Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/cpp_libs/sos3-2.lha/src/agg/Mapping.c

C/C++ Source or Header | 1992-01-23 | 113.4 KB | 2,769 lines

/* --------------------------------------------------------------------------
 * Copyright 1992 by Forschungszentrum Informatik (FZI)
 *
 * You can use and distribute this software under the terms of the licence
 * you should have received along with this program.
 * If not or if you want additional information, write to
 * Forschungszentrum Informatik, "STONE", Haid-und-Neu-Strasse 10-14,
 * D-7500 Karlsruhe 1, Germany.
 * --------------------------------------------------------------------------
 */
// **************************************************************************
// Module Mapping                   9/8/90                    Jochen Alt (ja)
//                                                   modified : 24/10/91 (bs)
//                                                   modified : 22/11/91 (ja)
// **************************************************************************
// implements methods of classes: Mapping, sos_Map_node
// **************************************************************************

#include "agg_err.h"
#include "trc_agg.h"
#include "sys.h"
#include "Mapping.h"
#include "agg_sos.h"

// erweiterbares Hash-Verfahren mit leichten Modifikationen
// Quelle : Datenbankhandbuch Seite 247
// siehe externe Dokumentation

#define get_key_based_on_equal()  get_role1_based_on_equal()
#define get_info_based_on_equal() get_role2_based_on_equal()
#define set_key_based_on_equal(b)  set_role1_based_on_equal(b)
#define set_info_based_on_equal(b) set_role2_based_on_equal(b)

inline int absolute(int d) { return (d>0)?d:-d; }

const sos_Offset NIL=0;

// Da psm direkt benutzt wird, wird ein Datentyp  benoetigt, der
// anstelle der Objekte abgespeichert wird. Dies ist ein object_save_t,
// der augenblicklich als sos_Typed_id definiert ist. Die beiden Operatoren,
// die object_save_t in sos_Object und umgekehrt konvertieren, sind
// make_object_save und make_Object
// **************************************************************************
object_save_t make_object_save (sos_Object o)
// **************************************************************************
// nimm das sos_Object o, bastle daraus ein object_save, und
// liefere es in os zurueck
{  sos_Typed_id  tpid = o.typed_id();
   object_save_t os;
   bcopy_from_sos_Typed_id(&tpid,&os);
   return os;
}

// **************************************************************************
sos_Object make_Object (object_save_t &os)
// **************************************************************************
// nimm den object_save os, mache daraus ein sos_Object und liefere es zurueck
{  sos_Typed_id tpid;
   bcopy_to_sos_Typed_id(&tpid,&os);
   return sos_Object::make(tpid);
}

/*
Abhaengig von sos_Bool:list_cursor gibt es zwei Versionen eines Mappings:
1. Version: list_cursor = FALSE
   Die Cursoroperatoren sind nur auf einem statischen Mapping
   definiert. Wird ein Objekt eingefuegt, so kan sich die Cursor-Reihenfolge
   voellig veraendern. Damit ist ein sinnvoller Umgang mit Cursorn nur auf
   einem sich nicht veraendernden Mapping moeglich. Sobald etwas eingefuegt
   oder geloescht wird, sind die Cursor zu schliessen und neu von vorne
   zu beginnen. Die Reihenfolge der Objekte ist durch die
   Reihenfolge in der Hashtabelle definiert, also fuer den Benutzer rein
   zufaellig. In dieser Version braucht ein Eintrag 36 Byte (= 2x sos_Object
   und ein Hashwert a 4 byte)
2. Version : list_cursor = TRUE
   Die Cursor-Operatoren koennen auch an einem dynamischen Mapping gleich-
   zeitig ausgefuehrt werden. Die einzelnen Eintraege sind miteinander
   doppelt verkettet, ein Einfuegen erfolgt am Anfang der Liste. Ein Eintrag
   braucht damit 36+2x16 = 68 Byte (zusaetzlich ein Vorwaerts und ein
   Rueckwaertszeiger). Damit werden die Prozeduren remove_at, insert_before
   und insert_after sinnvoll. In der Implementierung wird auf einer Seite
   die struct-Komponente list, bestehend aus den beiden Verweisen
   zusaetzlich abgespeichert.

In Funktionen, die ein Objekt zurueckliefern sollen, jedoch keines zum Liefern
haben, wird my_no_object als Ruckgabeparameter von benutzt. Weiterhin dient
my_no_object als Ende-der-Liste Marke im ersten und letzten Element des
Mappings. Kurzum, my_no_object ist ein Mapping- lokales NO_OBJECT, und dient
dazu, das Einfuegen von NO_OBJECT zu ermoeglichen.  Stattdessen kann man eben
my_no_object nicht einfuegen. Faktisch wird my_no_object immer mit dem
augenblicklich benutzten Mapping initialisiert, so dass ein Mapping nicht in
sich selbst eingefuegt werden kann. Dieses wird entsprechend abgefangen.
*/

#define PAGE_SIZE(list_cursor) \
   (list_cursor?page_size_with_list: page_size_without_list)

// max_page_entries = die maximale Anzahl an Eintraegen auf einer Seite
#define MAX_PAGE_ENTRIES(list_cursor) \
   (list_cursor? max_page_entries_with_list: max_page_entries_without_list)

// aus einer gegebenen Position in der Hashtabelle und der lokalen Tiefe
// der zugehoerigen Seitenliste kann die erste Position in der Hashtabelle
// berechnet werden, die auf diesselbe Seitenliste zeigt.
#define FIRST_LINK(ht_pos,local_depth) \
   ((LSHIFT(1,local_depth)-1) BITAND ht_pos)

/* ***********    Implementierung von sos_Map_node    *********************
Ein sos_Map_node enthaelt nur die Komponente sos_Object:key_val, die
dasjenige Objekt angibt, auf das der Cursor augenblicklich zeigt.
Ein sos_Map_node ist eindeutig einem Cursor zugeordnet und liegt
in dessen Container. Ist der Cursor ungueltig, so ist die Komponente
Cursor->get_key_val() == NO_OBJECT, andernfalls zeigt sie auf einen
sos_Map_node. Also wird beim Starten auf einem Mapping mit Inhalt ein
sos_Map_node erzeugt und dem Cursor zugeordnet, beim Verlassen des
letzten gueltigen Elements wird der sos_Map_node wieder geloescht.
*/


// **************************************************************************
sos_Int hash_id (sos_Object o)
// **************************************************************************
// benutzt die Adresse des Objektes, um daraus eine Zahl zu basteln

// Offsets liegen  nur auf durch 8 teilbaren Addressen
// => die ersten 3 Bit sind nutzlos, wird sie weg.
// Ist das Objekt aber keine Klassen-Instanz, sondern
// ein externes Objekt (z.B. sos_Int,sos_Char),
// so wird der Offset benutzt, indem der Wert steht.
{  sos_Int h = o.offset();
   if (o.container() != UNUSED_CONTAINER)
      h = RSHIFT(h,3) BITXOR sos_Int(o.container());

   return h;
} // ** hash_id **


// **************************************************************************
ht_entry_t read_ht_entry(sos_Container ct,
                         sos_Offset ht_offset,
                         sos_Int ht_pos)
// **************************************************************************
{  union {sos_Offset dummy;
      char       mem [HT_ENTRY_SIZE];} u;
   ct.read(ht_offset+ht_pos*HT_ENTRY_SIZE, HT_ENTRY_SIZE, &u);
   ht_entry_t ht_entry;
   bcopy_to_sos_Offset(&ht_entry.page_list_offset,&u.mem[0]);
   bcopy_to_sos_Char(&ht_entry.local_depth, &u.mem[SOS_OFFSET_SIZE] );
   return ht_entry;
} // ** read_ht_entry **

// **************************************************************************
void write_ht_entry(sos_Container ct,
                    sos_Offset ht_offset,
                    sos_Int ht_pos,
                    ht_entry_t ht_entry)
// **************************************************************************
{  union {sos_Offset dummy;
      char       mem [HT_ENTRY_SIZE];} u;

   bcopy_from_sos_Offset(&ht_entry.page_list_offset, &u.mem[0]);
   bcopy_from_sos_Char(&ht_entry.local_depth, &u.mem[SOS_OFFSET_SIZE]);
   ct.write(ht_offset+ht_pos*HT_ENTRY_SIZE, HT_ENTRY_SIZE, &u);
} // ** write_ht_entry **


// **************************************************************************
page_header_t  read_page_header(sos_Container ct, sos_Offset page_offset)
// **************************************************************************
{  union {sos_Offset dummy;
      char       mem [PAGE_HEADER_SIZE];} u;

   page_header_t page_header;
   ct.read (page_offset, PAGE_HEADER_SIZE, &u);
   bcopy_to_sos_Offset(&page_header.next_page, &u.mem[0]);
   bcopy_to_sos_Char(&page_header.pages, &u.mem[SOS_OFFSET_SIZE]);
   bcopy_to_sos_Char(&page_header.entries_on_last_page,
             &u.mem[SOS_OFFSET_SIZE+CHAR_SIZE]);

   return page_header;
} // ** read_page_header **

// **************************************************************************
void write_page_header(sos_Container ct,
                       sos_Offset page_offset,
                       page_header_t& page_header)
// **************************************************************************
{  union {sos_Offset dummy;
      char       mem [PAGE_HEADER_SIZE];} u;

   bcopy_from_sos_Offset(&page_header.next_page,&u.mem[0]);
   bcopy_from_sos_Char(&page_header.pages,&u.mem[SOS_OFFSET_SIZE]);
   bcopy_from_sos_Char(&page_header.entries_on_last_page,
               &u.mem[SOS_OFFSET_SIZE+CHAR_SIZE]);
   ct.write (page_offset, PAGE_HEADER_SIZE, &u);
} // ** write_page_header **


/*
Eine Seitenliste besteht aus einzelnen Seiten des Typs page_t, wobei
diese durch Vorwaertszeiger verkettet sind. Auf jeder Seite befindet sich
ein Seitenkopf mit den Angaben:

        sos_Char       pages;
           => Anzahl der Seiten in der Seitenliste
        sos_Char       entries_on_last_page;
           => Eintraege auf der letzten Seite, alle anderen Seite sind
              voll, d.h. sie haben max_page_entries Eintraege. Diese Angabe
              wird nur auf der ersten Seite verwaltet, auf den restlichen
              Seiten ist entries_on_last_page undefiniert.
        sos_Offset next_page;
           => Verweis auf die naechste Seite, bei der letzten Seite
              undefiniert.
*/


// **************************************************************************
void destroy_page_list(sos_Bool      list_cursor,
                       sos_Container ct,
                       sos_Offset    page_offset,
                       sos_Int       no_of_pages)
// **************************************************************************
// deallokiere im Container ct die Seitenliste bestehend aus den
// Typen page_t, wobei die erste zu deallokierende Seite auf page_offset
// liegt. Insgesamt sind no_of_pages Seiten  zu loeschen.
{  sos_Offset act_page_offset = page_offset;
   sos_Offset next_page_offset;
   for (sos_Int i=1;i<=no_of_pages;i++)
   {     // Lese zuerst naechsten Verweis, bevor die Seite deallokiert wird
      page_header_t page_header = read_page_header(ct, act_page_offset);
      next_page_offset = page_header.next_page;

      ct.deallocate(act_page_offset,PAGE_SIZE(list_cursor));
      act_page_offset = next_page_offset;
   }
} // ** destroy_page_list **


// **************************************************************************
void read_page( sos_Bool      list_cursor,
                sos_Container ct,
                sos_Offset    page_offset,
                sos_Int       no_of_entries,
                page_t&       page)
// **************************************************************************
// Lese Seite ab sos_Offset page_offset. Es werden no_of_entries
// Eintraege eingelesen.
{  err_assert((no_of_entries>=0 AND no_of_entries<=MAX_PAGE_ENTRIES(list_cursor)),
      "Mapping:read_page_entry::internal Error");
   page.page_header = read_page_header(ct,page_offset);
   union {sos_Typed_id dummy;
      char         mem [MAX_PAGE_SIZE];} u;
   ct.read(page_offset+PAGE_HEADER_SIZE, no_of_entries*ENTRY_SIZE,&u);
   char *ptr = u.mem;
   for (int i = 0;i<no_of_entries;i++)
   {  bcopy_to_sos_Typed_id(&page.entry[i].key,ptr);
      ptr += SOS_TYPED_ID_SIZE;
      bcopy_to_sos_Typed_id(&page.entry[i].info,ptr);
      ptr += SOS_TYPED_ID_SIZE;
      bcopy_to_sos_Int(&page.entry[i].hash_value,ptr);
      ptr += INT_SIZE;
   }

   if (list_cursor)
   {     // Lese die Vorgaenger und Nachfolger Verweise
      ptr = u.mem;
      ct.read(page_offset+add_list_pos, no_of_entries*LIST_SIZE, &u);
      for (int i = 0; i < no_of_entries; i++)
      {  bcopy_to_sos_Typed_id(&page.list[i].pred,ptr);
         ptr += SOS_TYPED_ID_SIZE;
         bcopy_to_sos_Typed_id(&page.list[i].succ,ptr);
         ptr += SOS_TYPED_ID_SIZE;
      }
   }
} // ** read_page **

// **************************************************************************
sos_Int read_page( sos_Bool      list_cursor,
                   sos_Container ct,
                   page_header_t first_page_header,
                   ht_entry_t    ht_entry,
                   sos_Int       page_no,
                   page_t&       page)
// **************************************************************************
// Lese die page_no.te Seite, auf die der Hashtabelleneintrag ht_entry
// zeigt, wobei der Seitenkopf der ersten Seite schon unter
// first_page_header bekannt ist.
{  sos_Offset page_offset = ht_entry.page_list_offset;
   page.page_header = first_page_header;

      // Durchlaufe Seitenliste bis zur richtigen Seite
   for (sos_Int no = 1; no < page_no; no++)
   { if (no >1)
         page.page_header = read_page_header(ct,page_offset);
      page_offset =page.page_header.next_page;
   }
   sos_Int entries = (page_no < first_page_header.pages)?
                     MAX_PAGE_ENTRIES(list_cursor):
                     first_page_header.entries_on_last_page;
   read_page(list_cursor, ct, page_offset, entries, page);

   return entries;
} // ** read_page **

// **************************************************************************
void read_page_entry(sos_Bool      list_cursor,
                     sos_Container ct,
                     sos_Int       page_offset,
                     sos_Int       entry_no,
                     page_t&       page)
// **************************************************************************
// Lese auf der Seite auf page_offset den entry_no.ten Eintrag in page
{  err_assert((entry_no>=0 AND entry_no<=MAX_PAGE_ENTRIES(list_cursor)),
      "Mapping::read_page_entry::internal Error");
   union {sos_Typed_id dummy;
      char         mem[ENTRY_SIZE];} u; // note: ENTY_SIZE > LIST_SIZE

   ct.read( page_offset+PAGE_HEADER_SIZE+entry_no*ENTRY_SIZE,
            ENTRY_SIZE,&u);
   bcopy_to_sos_Typed_id(&page.entry[entry_no].key,&u.mem[0]);
   bcopy_to_sos_Typed_id(&page.entry[entry_no].info,&u.mem[SOS_TYPED_ID_SIZE]);
   bcopy_to_sos_Int(&page.entry[entry_no].hash_value,
            &u.mem[SOS_TYPED_ID_SIZE+SOS_TYPED_ID_SIZE]);

   if (list_cursor)
   {  ct.read( page_offset+add_list_pos+entry_no*LIST_SIZE,
               LIST_SIZE,&u);
      bcopy_to_sos_Typed_id(&page.list[entry_no].pred,&u.mem[0]);
      bcopy_to_sos_Typed_id(&page.list[entry_no].succ,
                            &u.mem[SOS_TYPED_ID_SIZE]);
   }
} // ** read_page_entry **

// **************************************************************************
void write_page(sos_Bool      list_cursor,
                sos_Container ct,
                sos_Offset    page_offset,
                sos_Int       no_of_entries,
                page_t&       page)
// **************************************************************************
// Schreibe die Seite page mit no_of_entries Eintraegen
// an die Stelle page_offset
{  write_page_header(ct,page_offset,page.page_header);
   err_assert((no_of_entries>=0 AND no_of_entries<=MAX_PAGE_ENTRIES(list_cursor)),
      "Mapping::write_page::internal Error");

   union {sos_Typed_id dummy;
      char           mem [MAX_PAGE_SIZE];} u;
   char *ptr = u.mem;
   for (int i = 0; i < no_of_entries; i++)
   {  bcopy_from_sos_Typed_id(&page.entry[i].key,ptr);
      ptr += SOS_TYPED_ID_SIZE;
      bcopy_from_sos_Typed_id(&page.entry[i].info,ptr);
      ptr += SOS_TYPED_ID_SIZE;
      bcopy_from_sos_Int(&page.entry[i].hash_value,ptr);
      ptr += INT_SIZE;
   }
   ct.write(page_offset+PAGE_HEADER_SIZE, no_of_entries*ENTRY_SIZE,&u);

   if (list_cursor)
   {  ptr = u.mem;
      for (int i = 0; i < no_of_entries; i++)
      {  bcopy_from_sos_Typed_id(&page.list[i].pred,ptr);
         ptr += SOS_TYPED_ID_SIZE;
         bcopy_from_sos_Typed_id(&page.list[i].succ,ptr);
         ptr += SOS_TYPED_ID_SIZE;
      }
      ct.write(page_offset+add_list_pos, LIST_SIZE*no_of_entries, &u);
   }
} // ** write_page **

// **************************************************************************
void write_page_entry(sos_Bool      list_cursor,
                      sos_Container ct,
                      sos_Int       page_offset,
                      sos_Int       entry_no,
                      page_t&       page)
// **************************************************************************
// Schreibe auf der Seite page den einzelnen Eintrag Nr entry_no
// auf die Platte, der Seitenanfang beginnt bei page_offset.
{  err_assert((entry_no>=0 AND entry_no<=MAX_PAGE_ENTRIES(list_cursor)),
      "Mapping::write_page::internal Error");
   union {sos_Typed_id dummy;
      char         mem[ENTRY_SIZE];} u; // note: ENTY_SIZE > LIST_SIZE

   bcopy_from_sos_Typed_id(&page.entry[entry_no].key,&u.mem[0]);
   bcopy_from_sos_Typed_id(&page.entry[entry_no].info,
                           &u.mem[SOS_TYPED_ID_SIZE]);
   bcopy_from_sos_Int(&page.entry[entry_no].hash_value,
              &u.mem[SOS_TYPED_ID_SIZE+SOS_TYPED_ID_SIZE]);

   ct.write( page_offset+PAGE_HEADER_SIZE+entry_no*ENTRY_SIZE,
             ENTRY_SIZE,&u);
   if (list_cursor)
   {  bcopy_from_sos_Typed_id(&page.list[entry_no].pred,&u.mem[0]);
      bcopy_from_sos_Typed_id(&page.list[entry_no].succ,
                              &u.mem[SOS_TYPED_ID_SIZE]);
      ct.write( page_offset+add_list_pos+entry_no*LIST_SIZE, LIST_SIZE,&u);
   }
} // ** write_page_entry **

// search_page_for_key__F8sos_BoolR6page_tiiG10sos_Object
// **************************************************************************
sos_Int search_page_for_key(sos_Bool     key_based_on_equal,
                            page_t&      page,
                            sos_Int      entries,
                            sos_Int      org_hash_value,
                            sos_Object   key)
// **************************************************************************
// durchsucht die Seite page mit entries Eintraegen nach dem sos_Object key,
// das den Hashwert org_hash_value besitzt. Wird es gefunden, wird seine
// Position in der Seite geliefert, ansonsten -1.
{  T_PROC("search_page_for_key");
   TT(agg_M, T_ENTER);

   sos_Bool found = FALSE;
   for (sos_Int i=0;
        ((i<entries) AND (NOT found));
        i++)
   {  if (page.entry[i].hash_value == org_hash_value)
      {  sos_Object o = make_Object(page.entry[i].key);
         if (agg_same_entity(o, key, key_based_on_equal, EQ_STRONG))
         {  found = TRUE;
            TT(agg_M, T_LEAVE);
            return i;
         }
      }
   }

   TT(agg_M, T_LEAVE);
   return -1;
} // ** search_page_for_key **

// **************************************************************************
sos_Offset new_page_list(sos_Container ct, sos_Bool list_cursor)
// **************************************************************************
// allokiere eine neue Seitenliste und liefere deren sos_Offset zurueck
{  T_PROC("new_page_list");
   TT(agg_L, T_ENTER);

   sos_Offset new_page_offset = ct.allocate(PAGE_SIZE(list_cursor));
   page_header_t page_header;
   page_header.entries_on_last_page = 0;
   page_header.pages = 1;
   write_page_header(ct,new_page_offset, page_header);

   TT(agg_L, T_LEAVE);
   return new_page_offset;
} // ** new_page_list **

// **************************************************************************
void sos_Object_sos_Object_Mapping::write_succ_pred(
                                      sos_Container ct,
                                      sos_Bool      key_based_on_equal,
                                      sos_Bool      list_cursor,
                                      sos_Object    key,
                                      sos_Bool      write_succ,
                                      sos_Object    succ_pred)
// **************************************************************************
// Schreibe in den Vorgaeger bzw. Nachfolger von key succ_pred.
// Ob Vor oder Nachgaenger ausgewaehlt wird, wird durch write_succ
// geregelt. write_succ == TRUE schreibt succ_pred in den
// Nachfolgerzeiger von key, ansonsten in den Vorgaengerzeiger von key.
{  T_PROC("Mapping::write_succ_pred");
   TT(agg_M, T_ENTER);
   sos_Object my_no_object = self;
   if (my_no_object == key)
   {  TT(agg_M, T_LEAVE);
      return;
   }

   sos_Int org_hash_value = absolute((key_based_on_equal)?
                                      key.hash_value():hash_id(key));
   sos_Int ht_pos = org_hash_value MOD self.get_ht_entries();
   ht_entry_t ht_entry = read_ht_entry(ct,self.get_ht_offset(),ht_pos);

   sos_Offset page_offset = ht_entry.page_list_offset;
   page_header_t first_page_header = read_page_header(ct, page_offset);
   sos_Int pages = first_page_header.pages;
   sos_Int entries_on_last_page = first_page_header.entries_on_last_page;

   sos_Int pos = -1; // entspricht "nicht gefunden"
   sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
   page_t page;
   for (sos_Int page_no = 1;
        (page_no<=pages) AND (pos == -1);
        page_no++)
   {  if (page_no == pages)
     entries_on_page = entries_on_last_page;

      read_page(TRUE, ct, page_offset, entries_on_page, page);
      sos_Int pos = search_page_for_key ( key_based_on_equal,page,
                                          entries_on_page,
                                          org_hash_value, key );
      if (pos == -1)
         page_offset = page.page_header.next_page;
      else
      {     // Objekt gefunden
         if (write_succ)
            page.list[pos].succ = make_object_save(succ_pred);
         else
            page.list[pos].pred = make_object_save(succ_pred);
         write_page_entry(TRUE, ct,page_offset,pos, page);
      }
   }
   TT(agg_M, T_LEAVE);
} // ** Mapping::write_succ_pred **


// **************************************************************************
sos_Offset increase_page_list( sos_Bool       list_cursor,
                               sos_Container  ct,
                               sos_Offset     first_page_offset,
                               page_header_t& first_page_header,
                               sos_Offset     last_page_offset)
// **************************************************************************
// Eine Seitenliste, die an der Stelle ht_pos an der Hashtabelle
// angehaengt ist, wird um eine Seite erweitert. diese Seite wird
// hinten angehaengt. Ein Verweis auf die bisher letzte Seite
{  T_PROC("increase_page_list");
   TT(agg_M, T_ENTER);

   sos_Offset new_page_offset = ct.allocate(PAGE_SIZE(list_cursor));

      // Eigentlich sollte der Fall der Seitenlisten gaenzlich vermieden
      // werden. Wird nun eine Seitenliste tatsaechlich ueber 126 Seiten
      // gross, so ist entweder die Statistik fehlerhaft, oder es
      // sind tatsaechlich mehr als 3225 Eintraege mit demselben Hashwert im
      // Mapping. Diese Faelle fuehren zum Absturz, da die Variable, die die
      // Seiten in einer Seitenliste zaehlt, ein char ist. Ansich ist eine
      // solche Konstellation jedoch nicht vorstellbar.
   if (first_page_header.pages >= 126)
      err_raise(err_SYS, "statistical Error","Mapping:insert");

   first_page_header.pages++;
   first_page_header.entries_on_last_page = 0;

      // Existierte bisher nur eine Seite ?
   if (first_page_header.pages == 2)
      first_page_header.next_page = new_page_offset;
   else
   {     // Es gab schon mehr als eine Seite, der erste Seitenheader und
         // der Header der bisher letzten Seite muss geschrieben werden
      page_header_t last_page_header;
      last_page_header.next_page = new_page_offset;
      write_page_header(ct,last_page_offset, last_page_header);
   }
   write_page_header(ct,first_page_offset, first_page_header);

   TT(agg_M, T_LEAVE);
   return new_page_offset;
} // ** Mapping::increase_page_list

/*
Um zu entscheiden, ob die Hashtabelle geschrumpft werden kann, muss bekannt
sein, ob es Seitenlisten gibt, auf die nur ein HT-Eintrag verweist. Falls ja,
ist ein Schrumpfen nicht moeglich. Da beim Teilen und Splitten einer Seite
die lokale Tiefe veraendert wird, muss fuer jede moegliche lokale Tiefe
die Anzahl der Verweise gespeichert werden, da beim Splitten 2 Seiten
mit hoeheren lokalen Tiefen dazukommen und eine mit einer niedrigeren weg-
faellt.
Es gibt also einen von Hand allokierten Platz, auf dessen Anfang
get_no_of_pages_offset() zeigt. In den ersten 4 Byte davon steht die Anzahl
der Seitenlisten mit lokaler Tiefe 0 , in den naechsten 4 Byte die Anzahl mit
lokaler Tiefe 1 etc. bis MAX_GLOBAL_DEPTH.
*/

// **************************************************************************
sos_Bool no_single_referenced_pages(sos_Container ct,
                                    sos_Offset    no_of_pages_offset,
                                    sos_Int       global_depth)
// **************************************************************************
// liefert TRUE, falls es keine Seitenliste gibt, die von der Hashtabelle
// nur von einem einzigen Verweis referenziert wird. Dies wird anhand
// der Zaehler festgestellt, die fuer jede lokale Tiefe zaehlen, wieviel
// Seitenlisten es mit dieser lokalen Tiefe gibt. Die Seitenlisten,  die
// nur von einem Verweis referenziert werden, zeichnen sich durch
// lokale Tiefe == globale Tiefe aus.
{  sos_Int entry;
   union {sos_Int dummy;
      char    mem [INT_SIZE];} u;
      // lese die Anzahl der Verweise auf Seitenlisten der lokalen
      // Tiefe global_depth
   ct.read(no_of_pages_offset+INT_SIZE*global_depth,INT_SIZE,&u);
   bcopy_to_sos_Int(&entry,&u);
   return sos_Bool (entry == 0);
} // ** Mapping::no_single_referenced_pages **

// **************************************************************************
void add_no_of_pages(sos_Container ct,
                     sos_Offset    no_of_pages_offset,
                     sos_Int       local_depth,
                     sos_Int       value)
// **************************************************************************
// zaehle zu der Anzahl von Verweisen auf eine Seitenliste mit der
// lokalen Tiefe local_depth value dazu.
{  sos_Int entry;
   union {sos_Int dummy;
      char    mem [INT_SIZE];} u;

   sos_Int offset = no_of_pages_offset+INT_SIZE*local_depth;
   ct.read(offset, INT_SIZE, &u);
   bcopy_to_sos_Int(&entry,&u);
   entry += value;
   bcopy_from_sos_Int(&entry,&u);
   ct.write(offset, INT_SIZE, &u);
} // ** add_no_of_page **


// **************************************************************************
void sos_Object_sos_Object_Mapping::insert_in_page_list (
                                        sos_Container ct,
                                        sos_Bool      key_based_on_equal,
                                        sos_Bool      list_cursor,
                                        sos_Offset    page_list_offset,
                                        sos_Int       org_hash_value,
                                        sos_Object key, sos_Object info,
                                        sos_Object pred, sos_Object succ)
// **************************************************************************
// traegt einen Eintrag in eine Seitenliste ein und ersetzt
// geg. einen alten. Auf der Seitenliste muss Platz sein
{  T_PROC("Mapping::insert_in_page_list");

   page_t page;
   sos_Offset page_offset = page_list_offset;

      // Befindet sich der key bereits auf der Seite, so wird er durch
      // den neuen Eintrag ersetzt. Schaue also nach

   sos_Int pos = -1; // entspricht "nicht gefunden"
   sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);

   page.page_header = read_page_header(ct,page_offset);

   page_header_t first_page_header = page.page_header;
   sos_Int pages = first_page_header.pages;
   sos_Int entries_on_last_page = first_page_header.entries_on_last_page;
   for (sos_Int page_no=1;
        (page_no <= pages) AND (pos == -1);
        page_no++)
   {  if (page_no == pages)
     entries_on_page = entries_on_last_page;
      read_page(list_cursor, ct,page_offset, entries_on_page, page);
      pos = search_page_for_key (key_based_on_equal, page,
                                 entries_on_page, org_hash_value,key);
      if ((pos == -1) AND (page_no < pages))
         page_offset = page.page_header.next_page;
   }

      // Falls der Eintrag ersetzt wird, so wird er an diese
      // Stelle eingesetzt. Ansonsten wird er auf der
      // letzten Seite eingetragen und die H-Tabelle korrigiert

   sos_Int write_pos = pos;
   if (pos == -1)
   {     // Eintrag nicht gefunden, also schreibe ihn auf die letzte Seite.
         // Da die gesamte Liste durchgegangen wurde, ist page_offset
         // die Adresse der letzten Seite.

         // korrigiere Seitenheader der ersten Seite
      first_page_header.entries_on_last_page++;
      write_page_header(ct,page_list_offset,first_page_header);

      write_pos = entries_on_page;
      self.set_cardinality(self.get_cardinality() + 1);
   }

   page.entry[write_pos].hash_value = org_hash_value;
      // Falls der Key existiert wird er nicht nochmal eingetragen,
      // sondern nur der Entity ersetzt
   if (write_pos != pos)
      page.entry[write_pos].key = make_object_save(key);
   page.entry[write_pos].info = make_object_save(info);

      // Schreibe die Liste evt auf die Seite zurueck
   if (pos == -1)
   {  if (list_cursor)
      {     // schreibe in die Liste succ und pred
         page.list[write_pos].succ = make_object_save(succ);
         page.list[write_pos].pred = make_object_save(pred);
            // aktualisiere den Vorwaertszeiger von pred und den
            // Rueckwaertszeiger von succ
         self.write_succ_pred
            (ct, key_based_on_equal, list_cursor, pred, TRUE, key);
         self.write_succ_pred
            (ct, key_based_on_equal, list_cursor, succ, FALSE, key);

         if (self.get_cardinality() == 1)
         {     // erstes Element wird eingefuegt
            self.set_first_object(key);
            self.set_last_object(key);
         }
         else
         {  if (self.get_first_object() == succ)
               self.set_first_object(key);
            if (self.get_last_object() == pred)
               self.set_last_object(key);
         }
      }

         // schreibe den Eintrag auf der Seite zurueck
      write_page_entry(list_cursor, ct,page_offset, write_pos, page);
   }
   else
         // Der Eintrag war bereits vorhanden, nur der Entity wurde geaendert
         // schreibe den Eintrag auf der Seite zurueck
      write_page_entry(list_cursor, ct,page_offset, write_pos, page);

   TT(agg_M, T_LEAVE);
} // ** Mapping::insert_in_page_list **



// **************************************************************************
void sos_Object_sos_Object_Mapping::split_page(sos_Container ct,
                                               sos_Bool      list_cursor,
                                               sos_Offset    page_list_offset,
                                               sos_Char      par_local_depth,
                                               sos_Int       org_hash_value,
                                               sos_Int       nec_local_depth)
// **************************************************************************
// Eine Seitenliste wird solange gesplittet, bis der Seitenliste
// die neue lokale Tiefe nec(cessary)_local_depth zugeordnet wird.
// Saemtliche Seitenteilungen vor der letzten sind Seitenteilungen
// ohne Bewegungen von Objekten, denn wuerden Objekte bewegt,
// wuerde Platz geschaffen und somit waere nec_local_depth kleiner.
{  T_PROC("Mapping::split_page");
   TT(agg_M, T_ENTER);

   sos_Int global_depth = self.get_global_depth();
   sos_Offset no_of_pages_offset = self.get_no_of_pages_offset();
   sos_Offset ht_offset = self.get_ht_offset();

   sos_Int max_page_entries = MAX_PAGE_ENTRIES(list_cursor);
      // Teile die Seitenliste sooft wie noetig, d.h. allokiere neue
      // Seiten und biege die richtigen HT-Eintraege auf diese
      // Seiten um
   for (;par_local_depth <nec_local_depth;)
   {     // erzeuge neue leere Seite
      ht_entry_t new_ht_entry;
      new_ht_entry.page_list_offset = new_page_list(ct, list_cursor);
      sos_Int local_depth           = par_local_depth;
      sos_Int new_local_depth       = ++par_local_depth;
      new_ht_entry.local_depth      = new_local_depth;
      self.set_no_of_page_lists(self.get_no_of_page_lists() + 1);
      self.set_no_of_pages(self.get_no_of_pages() + 1);

      add_no_of_pages(ct,no_of_pages_offset,local_depth,-1);
      add_no_of_pages(ct,no_of_pages_offset,new_local_depth,2);

         // biege alle Eintraege der HT mit gesetztem
         // new_local_depth.ten Bit auf die neue Seite um

         // Wie lautet der der neuen Seite zugeordnete Hash-Wert-Teil ?
         // Nimm den alten Hash-Teil
      sos_Int old_hash_value_part = org_hash_value BITAND
                                    (LSHIFT(1,local_depth)-1);

         // Laufe alle Indexe durch, bei denen ein Verweis
         // auf die zu teilende Seitenliste steht. Das sind
         // 2^(global_depth-local_depth) Stueck.

         // Die Verweise werden abwechselnd belassen und umgebogen.
         // Da auf der alten Seitenliste die ersten nec_local_depth
         // Bit gleich sind, wird so begonnen, dass die alte Seitenliste
         // immer noch von der gleichen Stelle der
         // H-Tabelle erreicht wird (new_link)
      sos_Bool new_link = FALSE; // starte bei alter Seitenliste
      if ((org_hash_value BITAND LSHIFT(1,local_depth)) != 0)
         new_link = TRUE; // starte bei leerer Seite

         // wo ist der erste Verweis auf diese Seitenliste ?
      for (sos_Int k = 0;k<LSHIFT(1,global_depth-local_depth); k++)
      {     // verschiebe Laufindex k an richtige Position
            // vor dem Wert der Seite
         sos_Int j = LSHIFT(k,local_depth);
            // addiere den Hash-Teil der Seite dazu
         j = j BITOR old_hash_value_part;

         if (new_link)
               // Dieser Eintrag muss auf die neue
               // leere Seite umgebogen werden
            write_ht_entry(ct, ht_offset, j, new_ht_entry);
         else
         {     // Dieser Eintrag verbleibt,
               // lediglich die lokale Tiefe wird geaendert
            ht_entry_t tmp_ht_entry = read_ht_entry(ct, ht_offset, j);
            tmp_ht_entry.local_depth ++;
            write_ht_entry(ct,ht_offset,j, tmp_ht_entry);
         }
         new_link = (sos_Bool) (NOT new_link);
      }
   }

      // Da nur die letzte Seitenteilung hierbei beteiligt ist,
      // muessen also Seiteneintraege der alten Seitenliste
      // auf die bis jetzt leere Partnerseite.
      // Berechne Hash-Teil der alten Seitenliste
   sos_Int hash_value_part = org_hash_value BITAND
                             (LSHIFT(1,nec_local_depth)-1);
      // invertiere das nec_local_depth.te Bit => Partnerseite
   sos_Int ht_partner_pos = hash_value_part BITXOR
                            LSHIFT(1,nec_local_depth-1);

      // Lese den Offset der Partnerseite
   ht_entry_t ht_partner_entry = read_ht_entry(ct,ht_offset,ht_partner_pos);
      // Also: Die Eintraege kommen von ht_entry.page_list_offset
      //       nach ht_partner_entry.page_list_offset

      // Gehe die alte Seitenliste durch und schiebe jeden Seiteneintrag,
      // dessen Hashwert ein anderes nec_local_depth.tes Bit aufweist
      // als in org_hash_value, auf die neue Seitenliste

   sos_Offset old_page_offset  = page_list_offset;
   sos_Offset read_page_offset = old_page_offset;
   sos_Offset new_page_offset  = ht_partner_entry.page_list_offset;
   sos_Int bit                 = LSHIFT(1,nec_local_depth-1);
   sos_Int should_be_bit       = org_hash_value BITAND bit;

   page_t old_page;
   page_header_t old_page_header = read_page_header(ct,old_page_offset);
   old_page.page_header =    old_page_header;
   sos_Int old_entry_no     = 0;
   sos_Int old_page_no      = 1;
   sos_Bool add_old_page    = FALSE;

   page_t new_page;
   sos_Int new_entry_no     = 0;
   sos_Int new_page_no      = 1;

   page_header_t new_page_header = read_page_header(ct,new_page_offset);
   new_page.page_header = new_page_header;

   page_t r_page;
   page_header_t r_page_header = read_page_header(ct,read_page_offset);

   sos_Int no_of_pages = self.get_no_of_pages();
   for (sos_Int read_page_no=1;
        read_page_no <= r_page_header.pages;
        read_page_no++)
   {  sos_Int read_entries = (r_page_header.pages > read_page_no)?
                          max_page_entries:r_page_header.entries_on_last_page;
      read_page(list_cursor, ct,read_page_offset, read_entries, r_page);
      read_page_offset = r_page.page_header.next_page;

         // Gehe die alte Seite durch und kopiere die passenden Eintraege
         // auf die neue Seite.
      for (sos_Int read_no=0;read_no<read_entries;read_no++)
      {  if ((r_page.entry[read_no].hash_value BITAND bit) !=should_be_bit)
            {     // gesetztes  Bit => Eintrag auf neue Seite

                  // Ist neue Seite schon vollstaendig beschrieben ?
               if (new_entry_no == max_page_entries)
               {     // Falls die neue Seite bereits voll ist, erweitere Liste
                  sos_Offset last_page =
                     increase_page_list(list_cursor, ct,
                                        ht_partner_entry.page_list_offset,
                                        new_page_header, new_page_offset);

                  no_of_pages++;
                  new_page.page_header = new_page_header;
                  new_page.page_header.next_page = last_page;

                     // und schreibe die volle Seite aus
                  write_page(list_cursor, ct, new_page_offset,
                            max_page_entries, new_page);

                  new_entry_no = 0;
                  new_page_offset = last_page;
                  new_page_no++;

               }
               new_page.entry[new_entry_no] = r_page.entry[read_no];
                  // Falls list_cursor == FALSE schadet
                  // die folgende Zeile nichts
               new_page.list[new_entry_no++] = r_page.list[read_no];
            }
         else
            {     // Ist die alte Seite schon vollstaendig beschrieben ?
               if (old_entry_no == max_page_entries)
               {     // Ja, schreibe alte volle Seite aus
                  write_page(list_cursor, ct,
                             old_page_offset, max_page_entries, old_page);

                  old_page_no++;
                  old_page_offset = old_page.page_header.next_page;

                     // Lese den Vorwaertsverweis der naechsten Seite
                  if (old_page_no < old_page_header.pages)
                    old_page.page_header=read_page_header(ct,old_page_offset);

                  old_entry_no = 0;
               }
               old_page.entry[old_entry_no] = r_page.entry[read_no];
                  // Falls list_cursor == FALSE schadet
                  // die folgende Zeile nichts
               old_page.list[old_entry_no++] = r_page.list[read_no];
            }
      }
   }

   self.set_no_of_pages(no_of_pages);

      // Falls eine neue Seite noch nicht ausgeschrieben ist, tue dies
   if (new_entry_no > 0)
   {  new_page.page_header.entries_on_last_page = new_entry_no;
      new_page.page_header.pages = new_page_no;
      write_page(list_cursor, ct,new_page_offset, new_entry_no, new_page);
   }

      // Korrigiere Seitenheader der ersten neuen Seite
   new_page_header.entries_on_last_page = new_entry_no;
   new_page_header.pages = new_page_no;

      // Schreibe evt. den Seitenheader
   if ((new_page_header.pages > 1) OR (new_entry_no == 0))
      write_page_header(ct,ht_partner_entry.page_list_offset,new_page_header);


      // Falls eine alte Seite noch nicht ausgeschrieben wurde, tue dies
   if (old_entry_no > 0)
   {  old_page.page_header.entries_on_last_page = old_entry_no;
      old_page.page_header.pages = old_page_no;
      write_page(list_cursor, ct,old_page_offset, old_entry_no, old_page);
   }

      // Falls die alte Seitenliste eine volle Liste ist, lasse eine
      // leere Seite dranhaengen, da auf der alten Seitenliste ein
      // neuer Eintrag erfolgen soll.
   if (old_entry_no == max_page_entries)
   {  old_entry_no = 0;
      old_page_no++;
      add_old_page = TRUE;
   }

      // Korrigiere Seitenheader der ersten alten Seite
   old_page_header.entries_on_last_page = old_entry_no;
   old_page_header.pages = old_page_no;

      // Schreibe evt. alten Seitenheader
   if ((old_page_header.pages > 1) OR (old_entry_no == 0))
      write_page_header(ct,page_list_offset, old_page_header);

      // Gebe den Rest der alten Seitenliste frei
   if (old_page_no < r_page_header.pages)
   {  destroy_page_list(list_cursor, ct, old_page.page_header.next_page,
                        r_page_header.pages-old_page_no);
      self.set_no_of_pages(no_of_pages - (r_page_header.pages - old_page_no));
   }
   TT(agg_M, T_LEAVE);
} // ** Mapping::split_page **


// **************************************************************************
void sos_Object_sos_Object_Mapping::increase_hash_table()
// **************************************************************************
// erweitere die gesamte Hash-Tabelle, d.h. allokiere
// doppelt soviel Platz wie jetzt belegt wird, kopiere
// die alte Hash-Tabelle in die erste Haelfte und danach
// in die zweite Haelfte. => Auf jede Seite
// existieren zwei Verweise. Wirf die alte Hashtabelle weg
{  T_PROC("Mapping::increase_hash_table");
   TT(agg_M, T_ENTER);
   sos_Container ct = self.container();
   sos_Int old_ht_entries = self.get_ht_entries();
   sos_Int old_ht_size = old_ht_entries*HT_ENTRY_SIZE;
   sos_Offset new_ht_offset = ct.allocate(old_ht_size*2);

      // kopiere bisherige Hashtabelle zweimal
      // hintereinander in den neu allokierten Platz
   ct.copy(self.get_ht_offset(), old_ht_size, ct, new_ht_offset);
   ct.copy(self.get_ht_offset(), old_ht_size, ct, new_ht_offset+old_ht_size);

      // Wirf alte Hash-tabelle weg
   ct.deallocate(self.get_ht_offset(), old_ht_size);

      // markiere die Neue
   self.set_ht_offset(new_ht_offset);
   self.set_ht_entries(old_ht_entries * 2);
   self.set_global_depth(self.get_global_depth() + 1);
   TT(agg_M, T_LEAVE);
} // ** Mapping::increase_hash_table **

// increase_ht_structur__F8sos_Booliiiiii
// **************************************************************************
sos_Bool increase_ht_structur(sos_Bool list_cursor,
                              sos_Int global_depth,
                              sos_Int ht_entries,
                              sos_Int no_of_pages,
                              sos_Int length,
                              sos_Int local_depth,
                              sos_Int nec_local_depth)
// **************************************************************************
// entscheidet, ob wegen eines Seitenueberlaufs die HT-Struktur
// vergoessert werden soll, oder an die Seitenliste eine Seite
// angehaengt wird.
{
   T_PROC("increase_ht_structur");
   TT(agg_M, T_ENTER);

      // Falls die HT nicht vergroessert werden muesste, sondern
      // eine Seitenteilung reichen wuerde, plaediere immer fuer die
      // Erweiterung der HT
   if (global_depth >= nec_local_depth)
   {  TT(agg_M, T_LEAVE)
      return TRUE;
   }

      // Berechne den Platzbedarf bei Vergroesserung der HT-Struktur
   sos_Int page_size = PAGE_SIZE(list_cursor);
   sos_Int ht_memory; // Bei HT-Erweiterung
   sos_Int pl_memory; // Bei Seitenlisten Erweiterung

      // Bei normaler  Speicherausnutzung, d.h. Jede Seite ist
      // zur Haelfte gefuellt, gibt die Kennzahl 100, sonst > 100
      // Ist die Ausnutzung besser, gilt Kennzahl < 100

      // Bedarf der jetzigen Hashtabelle
   sos_Int ht_use = ht_entries*HT_ENTRY_SIZE;

      // Bedarf der jetzigen saemtlichen Seiten
   sos_Int page_lists_use = no_of_pages*page_size;

      // Berechne den Speicher, der beim Erweitern der HT-Struktur
      // zusaetzlich benoetigt wird

      // Fuer jedes Splitten kommt eine Seite dazu
   sos_Int increasing_use = (nec_local_depth-local_depth)*page_size;
      // Fuer das Erweitern der HT kommt immer die bisherige Groesse dazu
   increasing_use += (LSHIFT(1,nec_local_depth) - LSHIFT(1,global_depth))
                     *HT_ENTRY_SIZE;

   sos_Int ht_memory_used = ht_use + page_lists_use + increasing_use;
      // Bei der Alternative der Seitenliste kommt nur eine Seite dazu;
   sos_Int pl_memory_used = ht_use + page_lists_use + page_size;

      // Berechne den optimalen Platzbedarf. Er ergibt sich durch
      // zu drei/viertel gefuellte Seiten, wobei jeder Verweis auf genau
      // eine Seite zeigt.=> Berechne Anzahl der noetigen Seiten = Verweise,
      // plumitiziere mit Platzbedarf
   sos_Int opt_entries = MAX_PAGE_ENTRIES(list_cursor)*3/4;
   sos_Int opt_memory_used = (page_size + HT_ENTRY_SIZE)*
                         length/opt_entries;

   ht_memory = (ht_memory_used*100) / opt_memory_used;
   pl_memory = (pl_memory_used*100) / opt_memory_used;


      // Berechne die Kennzahl der Zeiteffizienz
      // Es wird die durchschnittliche Laenge einer Seitenliste berechnet
      // Falls keine Seitenlisten existieren, so ist die Effizienz
      // optimal. Die HT-Erweiterung ist in diesem Sinne optimal, auch wenn
      // durch fruehere Seitenlisten die Effizienz nicht 1000 entspricht,
      // ist der einzige moegliche Weg dorthin die HT-Erweiterung.

   sos_Int ht_eff = 100;
   sos_Int pl_eff = 100*(no_of_pages+1)/ht_entries;


      // Jetzt kommt die Entscheidung: Beide Kennzahlen
      // werden gleich gewichtet und verglichen
   sos_Bool result = FALSE;
   if ((ht_memory + ht_eff) <= (pl_memory + pl_eff))
      result = TRUE;

   TT(agg_M, T_LEAVE);
   return result;
} // ** Mapping::increase_ht_structur **


// **************************************************************************
sos_Int neccessary_local_depth(sos_Bool      list_cursor,
                               sos_Container ct,
                               sos_Bool      key_based_on_equal,
                               sos_Offset    page_list_offset,
                               sos_Char      local_depth,
                               sos_Offset&   last_page_offset,
                               sos_Int       org_hash_value,
                               sos_Object    key)
// **************************************************************************
// Es wird berechnet, welche lokale Tiefe eine volle Seitenliste
// plus dem einzufuegenden Objekt haben muesste, damit mindestens
// ein Seiten Eintrag abgespalten
// werden koennte. Oder: Es wird berechnet, bis zu welchem
// Bit im Hash-Wert nicht mehr alle Seiteneintraege gleich sind
// Wird dagegen ein Eintrag gefunden, der durch den neuen Eintrag
// ersetzt wuerde, so wird dieselbe lokale Tiefe zurueckgeliefert
{  T_PROC("neccessary_local_depth");
   TT(agg_M, T_ENTER);

   sos_Int hash_value = org_hash_value;
   sos_Int nec_local_depth = MAX_GLOBAL_DEPTH;
   sos_Offset page_offset = page_list_offset;

   page_header_t first_page_header;
   first_page_header = read_page_header(ct, page_list_offset);
   sos_Int pages = first_page_header.pages;
   sos_Int entries_on_last_page = first_page_header.entries_on_last_page;
   sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
      // Durchlaufe alle Seiten
   for (sos_Int page_no=1;
        (page_no<=pages);
        page_no++)
   {     // Diese Schleife darf nicht vorher abgebrochen werden, da
         // last_page_offset als Ausgabeparameter erwartet wird

      page_t page;
      if (page_no == pages)
     entries_on_page = entries_on_last_page;
      read_page(list_cursor, ct, page_offset,entries_on_page, page);

      last_page_offset = page_offset;
      page_offset = page.page_header.next_page;

         // Durchlaufe alle Eintraege auf dieser Seite
      for (sos_Int entry_no = 0;
           (entry_no < entries_on_page);
           entry_no++)
      {  sos_Int tmp_hash_value = page.entry[entry_no].hash_value;

         if (org_hash_value == tmp_hash_value)
         {  sos_Object o = make_Object(page.entry[entry_no].key);
            if (agg_same_entity (key, o,key_based_on_equal, EQ_STRONG))
            {     // das Objekt wuerde dieses Objekt ersetzen, also
               // keine Erhoehung der lokalen Tiefe notwendig
           TT(agg_M, T_LEAVE);
               return local_depth;
            }
         }
            // Ab dem wievielten Bit unterscheiden sich der bisherige
            // Hashwert und der aktuelle Eintrag ?
         sos_Int diff_hash_value = hash_value BITXOR tmp_hash_value;

            // Die Bits der lokalen Tiefe sind auf alle Faelle gleich,
            // also rechne erst ab local_depth+1;
         for (sos_Int i = local_depth+1;
              i<=nec_local_depth;
              i++)
            if ((RSHIFT(diff_hash_value, i-1) BITAND 1) == 1)
               nec_local_depth = i++;
      }
   }

   TT(agg_M, T_LEAVE);
   return nec_local_depth;
} // ** Mapping::neccessary_local_depth *

// insert_in_list__30_sos_Object_sos_Object_MappingR12sos_Typed_idG10sos_ObjectN32
// **************************************************************************
void sos_Object_sos_Object_Mapping::insert_in_list
                                       (sos_Object key, sos_Object info,
                                        sos_Object pred, sos_Object succ)
// **************************************************************************
// fuegt einen Eintrag ein und setzt ihn, falls list_cursor == TRUE
// in die durch pred und succ gegebenene Reihenfolge
{  T_PROC("Mapping::insert_in_list");
   TT(agg_M, T_ENTER);

      // Ist das Mapping leer, so existiert noch keine Hashtabelle
   if (self.get_ht_entries() == 0)
      self.init_table();

   sos_Container ct            = self.container();
   sos_Bool key_based_on_equal = self.get_key_based_on_equal();
   sos_Bool list_cursor        = self.get_list_cursor();
   sos_Int org_hash_value      = absolute((key_based_on_equal)?
                                          key.hash_value():hash_id(key));
   sos_Int ht_pos              = org_hash_value MOD self.get_ht_entries();
   sos_Offset ht_offset        = self.get_ht_offset();
   ht_entry_t ht_entry         = read_ht_entry(ct,ht_offset,ht_pos);

   page_header_t page_header   = read_page_header(ct,ht_entry.page_list_offset);

      // Ist die Seitenliste aufgefuellt ?
   if (page_header.entries_on_last_page < MAX_PAGE_ENTRIES(list_cursor))
         // Nein, es ist noch Platz
      self.insert_in_page_list(ct, key_based_on_equal, list_cursor,
                                ht_entry.page_list_offset, org_hash_value,
                                key, info, pred, succ);
   else
   {     // Die Seitenliste ist voll. Entweder wird die HT erweitert,
         // oder die Seitenliste wird um eine Seite vergroessert.
      sos_Offset last_page =0;
      sos_Int nec_local_depth =
          neccessary_local_depth( list_cursor, ct, key_based_on_equal,
                                  ht_entry.page_list_offset,
                                  ht_entry.local_depth,
                                  last_page, org_hash_value, key);

         // Falls der Eintrag einen anderen ersetzt, so
         // ist keine Erweiterung notwendig
      if (nec_local_depth == ht_entry.local_depth)
         self.insert_in_page_list(ct, key_based_on_equal, list_cursor,
                                   ht_entry.page_list_offset, org_hash_value,
                                   key, info, pred, succ);
      else
      {  if (increase_ht_structur
               (list_cursor,
                self.get_global_depth(),self.get_ht_entries(),
                self.get_no_of_pages(),self.get_cardinality(),
                ht_entry.local_depth, nec_local_depth))
         {     // Die Hash-Struktur wird vergroessert, erweitere
           // zuerst die Hashtabelle auf die benoetigten Groesse
            for (;self.get_global_depth() < nec_local_depth;)
               self.increase_hash_table(); // veraendert get_global_depth() !
               // Teile jetzt die Seiten. Hierbei sind alle Seitenteilungen
               // ohne Objektumschaufelungen verbunden, bis auf die letzte.
               // Drum der Parameter nec_local_depth
            self.split_page (ct, list_cursor,
                             ht_entry.page_list_offset, ht_entry.local_depth,
                             org_hash_value, nec_local_depth);

            ht_pos = org_hash_value MOD self.get_ht_entries();
            ht_entry = read_ht_entry(ct,self.get_ht_offset(), ht_pos);
            self.insert_in_page_list (ct, key_based_on_equal, list_cursor,
                                      ht_entry.page_list_offset,
                                      org_hash_value, key, info,
                                      pred, succ);
         }
         else
         {     // Die Seitenliste wird um eine Seite erweitert:
            increase_page_list(list_cursor, ct, ht_entry.page_list_offset,
                               page_header, last_page);
            self.set_no_of_pages(self.get_no_of_pages()+1);

            self.insert_in_page_list(ct, key_based_on_equal, list_cursor,
                                     ht_entry.page_list_offset,org_hash_value,
                                     key, info, pred, succ);
         }
      }
   }
   TT (agg_M,T_LEAVE);
} // ** Mapping:insert_in_list **

// remove_from_page_list__30_sos_Object_sos_Object_MappingR12sos_Typed_idG13sos_Container8sos_BoolT3UiiG10sos_Object
// **************************************************************************
sos_Object sos_Object_sos_Object_Mapping::remove_from_page_list
                                           (sos_Container ct,
                                            sos_Bool      list_cursor,
                                            sos_Bool      key_based_on_equal,
                                            sos_Offset    page_list_offset,
                                            sos_Int       org_hash_value,
                                            sos_Object    key)
// **************************************************************************
// Liefert sos_Bool_Object::TRUE, falls der Eintrag gefunden wurde. Der Entry
// wird nicht geliefert, da er sonst mit make_Object angefasst werden muesste,
// was er hier nicht soll.
{  T_PROC("Mapping::remove_from_page_list");
   TT(agg_M, T_ENTER);

   sos_Object my_no_object = self;
      // assume that key won't be found:
   sos_Object  found = make_sos_Bool_object(FALSE);
   page_t page;
   page_header_t page_header;
   sos_Offset page_offset = page_list_offset;
   sos_Offset prev_page_offset;
   page_header = read_page_header(ct, page_offset);
   sos_Int pages = page_header.pages;
   sos_Int entries_on_last_page = page_header.entries_on_last_page;
   sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
   sos_Int page_no = 1;
   sos_Int pos = -1; // entspricht "nicht gefunden";
   for (; (page_no<=pages) AND (pos == -1); page_no++)
   {  if (page_no == pages)
     entries_on_page = entries_on_last_page;
      read_page(list_cursor, ct, page_offset, entries_on_page, page);
      pos = search_page_for_key (key_based_on_equal, page,
                                 entries_on_page,
                                 org_hash_value,key);
      if (pos == -1)
      {  prev_page_offset  = page_offset;
         page_offset = page.page_header.next_page;
      }
   }

   page_no --;
      // Im Falle von based_on_equal == TRUE ist der key nicht unbedingt
      // derselbe wie der tatsaechlich eingetragene Schluessel. real_key
      // ist der Eingetragene. real_key ist fuer den Test auf Identitaet
      // mit dem ersten bzw. letzten Element notwendig.(Equal ginge auch,
      // dauert aber laenger).
   sos_Object real_key;

   if (pos != -1)
   {  found = make_sos_Bool_object(TRUE);
      real_key = make_Object(page.entry[pos].key);

      sos_Object pred,succ;
      if (list_cursor)
      {  pred = make_Object(page.list[pos].pred);
         succ = make_Object(page.list[pos].succ);
      }
      self.set_cardinality(self.get_cardinality() - 1);

         // Der zu loeschende Eintrag ist auf der letzten Seite
      if (page_no == page_header.pages)
      {     // fuelle die Luecke auf
         if (page_header.entries_on_last_page > 1)
         {     // und korrigiere den Seitenheader
            page.entry[pos] = page.entry[--page_header.entries_on_last_page];
            page.list[pos]  = page.list[page_header.entries_on_last_page];
               // schreibe Seiteneintrag zurueck
            write_page_entry(list_cursor, ct, page_offset, pos, page);
         }
         else
            // oder deallokiere die Seite
         {  if (page_header.pages > 1)
            {  ct.deallocate(page_offset, PAGE_SIZE(list_cursor));
               page_header.pages --;
               page_header.entries_on_last_page=MAX_PAGE_ENTRIES(list_cursor);
               self.set_no_of_pages(self.get_no_of_pages()-1);
            }
            else
               page_header.entries_on_last_page = 0;
        }
            // schreibe Seitenheader zurueck
         write_page_header(ct,page_list_offset, page_header);
      }
      else
      {     // Falls der Eintrag nicht auf der letzten Seite war, so nimm
            // einen Eintrag der letzten Seite und schreibe ihn in die Luecke
            // hangel dich zur letzten Seite vor
         sos_Offset last_page_offset = page.page_header.next_page;
         page_header_t tmp_page_header;
         page_no++;
         for (;page_no<page_header.pages;page_no++)
         {  tmp_page_header = read_page_header(ct, last_page_offset);
            last_page_offset = tmp_page_header.next_page;
         }

            // nimm von der letzten Seite den letzten Eintrag
            // und korrigiere nur den Seitenheader
         page_t tmp_page;
         read_page_entry(list_cursor, ct,last_page_offset,
                         --page_header.entries_on_last_page,
                         tmp_page);

            // und fuege ihn in die Luecke
         page.entry[pos] = tmp_page.entry[page_header.entries_on_last_page];
         page.list[pos]  = tmp_page.list[page_header.entries_on_last_page];

         write_page(list_cursor, ct,page_offset, pos+1, page);

            // Falls die letzte Seite jetzt leer ist, deallokiere
         if (page_header.entries_on_last_page == 0)
         {  ct.deallocate(last_page_offset, PAGE_SIZE(list_cursor));
            page_header.entries_on_last_page = MAX_PAGE_ENTRIES(list_cursor);
            page_header.pages--;
            self.set_no_of_pages(self.get_no_of_pages()-1);
         }

            // Schreibe den Seitenheader der ersten Seite zurueck
         write_page_header(ct,page_list_offset, page_header);
      }

      if (list_cursor)
      {     // fuege Objekt aus der Liste
         self.write_succ_pred
            (ct, key_based_on_equal, list_cursor, pred, TRUE, succ);
         self.write_succ_pred
            (ct, key_based_on_equal, list_cursor, succ, FALSE, pred);

         if (real_key == self.get_last_object())
            self.set_last_object(pred);
         if (real_key == self.get_first_object())
            self.set_first_object(succ);

            // Letztes Objekt:
         if (self.get_cardinality() == 0)
         {  sos_Object my_no_object = self;
            self.set_first_object(my_no_object);
            self.set_last_object(my_no_object);
         }
      }
   }

   TT(agg_M, T_LEAVE);
   return found;
} // ** Mapping::remove_from_page_list **



// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::assemble_page(
                                           sos_Offset page_list_offset,
                                           sos_Char   local_depth,
                                           sos_Int    org_hash_value)
// **************************************************************************
{  T_PROC("Mapping::assemble_page");
   TT(agg_M, T_ENTER);

   sos_Container ct         = self.container();
   sos_Bool list_cursor     = self.get_list_cursor();
   sos_Int max_page_entries = MAX_PAGE_ENTRIES(list_cursor);

   page_t page;
   page_t partner_page;
   ht_entry_t ht_partner_entry;

   page.page_header     = read_page_header(ct, page_list_offset);
   sos_Int ht_partner_pos;

   sos_Bool assemble_flag;
      // liefere zurueck, ob verschmolzen wurde
   sos_Bool result             = FALSE;
   sos_Bool act_page_is_read   = FALSE;

   do // while (assemble_flag)
   {  assemble_flag = FALSE;

         // zuerst eine Grob-Pruefung, ob eine Chance auf
         // Verschmelzung besteht:
         // Ist die Seitenliste nur eine Seite, und ist sie nur 3/4 voll,
         // und gibt es ueberhaupt eine Partnerseite ?
      if ((page.page_header.entries_on_last_page <= max_page_entries*3/4) AND
          (page.page_header.pages == 1) AND
          (local_depth > 0))
      {     // Berechne die Position der Partnerseite
         ht_partner_pos     = (org_hash_value BITAND LSHIFT(1,local_depth)-1)
                              BITXOR LSHIFT(1,local_depth-1);

            // Lese den HT-Eintrag der Partnerseite
         ht_partner_entry =
            read_ht_entry(ct,self.get_ht_offset(),ht_partner_pos);

            // Hat die Partnerseite die gleiche lokale Tiefe ?
         if (ht_partner_entry.local_depth == local_depth)
         {     // Ja
               // Lese Seitenkopf der Partner Seite
            partner_page.page_header =
                   read_page_header(ct, ht_partner_entry.page_list_offset);

               // Besteht die Partnerseite auch nur aus einer Seite ?
            if (partner_page.page_header.pages == 1)
            {  // passen alle Eintraege gut auf eine Seite ? (gut = 25% frei)
               assemble_flag = FALSE;
               if ((partner_page.page_header.entries_on_last_page+
                     page.page_header.entries_on_last_page)
                     <= max_page_entries*3/4)
                  assemble_flag = TRUE;
            }
         }
      }

      if (assemble_flag)
      {  result = TRUE;

         self.set_no_of_page_lists(self.get_no_of_page_lists() - 1);

         if (NOT (act_page_is_read))
         {  read_page(list_cursor, ct,page_list_offset,
                      page.page_header.entries_on_last_page, page);
            act_page_is_read = TRUE;
         }

            // Lese Partner-Seite
         read_page(list_cursor, ct,ht_partner_entry.page_list_offset,
                   partner_page.page_header.entries_on_last_page,
                   partner_page);

            // Kopiere die Eintraege der Partnerseite
            // auf die urspruengliche Seite
         for (sos_Int i=0; i<partner_page.page_header.entries_on_last_page;i++)
         {  page.entry[page.page_header.entries_on_last_page] =
               partner_page.entry[i];
            page.list[page.page_header.entries_on_last_page++] =
               partner_page.list[i];
         }

            // Korrigiere die Angabe, wieviel Seiten mit einer
            // bestimmten lokalen Tiefe existieren
         sos_Int no_of_pages_offset = self.get_no_of_pages_offset();
         add_no_of_pages(ct,no_of_pages_offset,local_depth,-2);
         add_no_of_pages(ct,no_of_pages_offset,local_depth-1,1);

            // Gib die Partnerseite frei
         ct.deallocate (ht_partner_entry.page_list_offset,
                        PAGE_SIZE(list_cursor));
         self.set_no_of_pages(self.get_no_of_pages()-1);

         write_page(list_cursor, ct,page_list_offset,
                    page.page_header.entries_on_last_page, page);

         sos_Int old_local_depth = local_depth --;

            // Die Hashtabelle muss korrigiert werden: Alle
            // Verweise auf die Partnerseite muessen auf die verschmolzene
            // Seite umgebogen werden
            // Wie lautet der der vereinigten Seite zugeordnete Hashwertteil ?
         sos_Int hash_value_part = ht_partner_pos BITAND
                               (LSHIFT(1,local_depth)-1);

            // Laufe alle Indexe durch, die auf die neue
            // vereinigte Seite zeigen. Diese Verweise werden
            // umgebogen
         sos_Int global_depth = self.get_global_depth();
         sos_Offset ht_offset = self.get_ht_offset();
         for (sos_Int k = 0;k<LSHIFT(1,global_depth-local_depth); k++)
         {     // verschiebe Laufindex k an richtige Position
               // vor dem Wert der Seite
            sos_Int j = LSHIFT(k,local_depth);
               // addiere hash-Teil der Seite dazu
            j = j BITOR hash_value_part;

               // Dieser Eintrag muss auf die neue Seite umgebogen werden
               // d.h. vielleicht zeigt er schon auf die Seite, aber
               // die lokale Tiefe ist in jedem Fall zu hoch
            ht_entry_t ht_entry;
            ht_entry.page_list_offset = page_list_offset;
            ht_entry.local_depth = local_depth;
            write_ht_entry(ct,ht_offset,j, ht_entry);
         }
      }
   }
   while (assemble_flag);

   TT(agg_M,T_LEAVE);
   return result;
} // ** Mapping::assemble_page **


// **************************************************************************
void sos_Object_sos_Object_Mapping::decrease_hash_table()
// **************************************************************************
// die Hash-tabelle kann genau dann halbiert werden, wenn
// keine Seiten existieren, die nur einen Verweis in der
// Hash-Tabelle besitzen
{
   T_PROC("Mapping::decrease_hash_table");
   TT(agg_M, T_ENTER);

   sos_Container ct              = self.container();
   sos_Int global_depth          = self.get_global_depth();
   sos_Offset no_of_pages_offset = self.get_no_of_pages_offset();

   for (;no_single_referenced_pages(ct,no_of_pages_offset,global_depth);)
   {     // Merke alte Tabellen-Position und Laenge
      sos_Int old_ht_entries   = self.get_ht_entries();
      sos_Int old_ht_size      = old_ht_entries*HT_ENTRY_SIZE;
      sos_Offset old_ht_offset = self.get_ht_offset();

         // definiere neue Tabellen Position und Laenge
      sos_Int new_ht_entries = old_ht_entries / 2;
      sos_Int new_ht_size   = new_ht_entries*HT_ENTRY_SIZE;
      sos_Int new_ht_offset = ct.allocate(new_ht_entries*HT_ENTRY_SIZE);
      self.set_ht_entries(new_ht_entries);
      self.set_ht_offset(new_ht_offset);

         // kopiere erste Haelfte der alten Tabelle in neue Tabelle
      ct.copy( old_ht_offset,new_ht_size,ct,new_ht_offset);
      global_depth--;

         // Gib alte Tabelle frei
      ct.deallocate(old_ht_offset,old_ht_size);
   }
   self.set_global_depth(global_depth);
   TT (agg_M,T_LEAVE);
} // ** decrease_hash_table

// **************************************************************************
sos_Bool get_entry (sos_Container  ct,
                    sos_Bool       list_cursor,
                    sos_Bool       key_based_on_equal,
                    sos_Int        ht_entries,
                    sos_Offset     ht_offset,
                    sos_Object&    key,
            sos_Bool       return_info,
            sos_Object&    info,
                    sos_Object&    pred,
                    sos_Object&    succ)
// **************************************************************************
// Setzt key und - falls list_cursor == TRUE - pred und succ auf die
// key-Objekte im gegebenen Mapping. Ergebnis ist das dem key entsprechende
// info. Es gilt agg_same_entity (key-vorher, key-nachher, key_based_on_equal)
// Wird return_info== TRUE uebergeben, wird info geliefert, ansonsten nicht.
// pred und succ werden nur im Falle von list_cursor == TRUE geliefert.

{  T_PROC("get_entry");
   TT(agg_M,T_ENTER; TI(ht_entries); TI(ht_offset));

   if (ht_entries>0)
   {  sos_Int org_hash_value  = absolute((key_based_on_equal)?
                                         key.hash_value() : hash_id(key));
      sos_Int ht_pos          = org_hash_value MOD ht_entries;
      ht_entry_t ht_entry     = read_ht_entry(ct,ht_offset,ht_pos);
      page_t page;

      sos_Offset page_offset  = ht_entry.page_list_offset;
      sos_Int pos = -1; // entspricht "nicht gefunden"

      page_header_t page_header = read_page_header (ct, page_offset);
      sos_Int pages = page_header.pages;
      sos_Int entries_on_last_page = page_header.entries_on_last_page;
      sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
      for (sos_Int page_no = 1; (page_no<=pages) AND (pos == -1); page_no++)
      {  if (page_no == pages)
        entries_on_page = entries_on_last_page;

         read_page(list_cursor, ct, page_offset, entries_on_page, page);
         pos = search_page_for_key ( key_based_on_equal, page, entries_on_page,
                                     org_hash_value, key );
         if (pos == -1)
            page_offset = page.page_header.next_page;
         else
         {  if (list_cursor)
            {  pred = make_Object(page.list[pos].pred);
               succ = make_Object(page.list[pos].succ);
           sos_Bool test1 = (succ == NO_OBJECT);
           sos_Bool test2 = (pred == NO_OBJECT);
            }
            key = make_Object(page.entry[pos].key);
            if (return_info)
           info = make_Object(page.entry[pos].info);

            TT(agg_M, T_LEAVE);
           // gefunden !
            return TRUE;
         }
      }
   }
   TT(agg_M,T_LEAVE);
      // nicht gefunden:
   return FALSE;
} // ** get_entry **

/*
Reihenfolge in der Hashtabelle:
Die Ordnung bezieht sich immer nur auf diejenigen Verweise in der Hashtabelle,
die die ersten Verweise auf eine bestimmte Seitenliste sind. Das Durchlaufen
mit einem Cursor funktioniert auf der Version mit list_cursor == FALSE so:
Die Cursor-Operatoren wurden ueberlagert, mit dem Oeffnen eines Cursors werden
die Prozeduren read_first_object und read_last_object aufgerufen, die das
erste und letzte Objekt liefern. open_cursor setzt nun die Variablen
first_object und last_object.  Beim Durchlaufen mit dem Cursor wird die
Hashtabelle solange durchsucht, bis ein Verweis gefunden wird, der der Erste
auf die referenzierte Seitenliste ist. Dies ist der Fall, wenn in der Position
der Hashtabelle (ht_pos) nur die ersten (lokale_tiefe) Bit gesetzt sind. Auf
der Seitenliste werden die Eintraege gemaess der Reihenfolge auf der Seite
durchlaufen. Nach dem letzten Eintrag auf der Seitenliste beginnt wieder die
Suche in der Hashtabelle nach einem ersten Verweis auf die naechste
Seitenliste.
*/

// **************************************************************************
sos_Object get_pred ( sos_Container  ct,
                      sos_Bool       key_based_on_equal,
                      sos_Object     my_no_object,
                      sos_Int        ht_entries,
                      sos_Offset     ht_offset,
                      sos_Object     key)
// **************************************************************************
// Diese Prozedur wird nur aufgerufen, wenn get_list_cursor() == FALSE,
// d.h. die Version ohne verkettung der Eintraege ist gefragt.
// Es wird das Objekt in der eben geschilderten Reihenfolge nach key
// geliefert.
{  sos_Int org_hash_value  =absolute((key_based_on_equal)?
                                      key.hash_value() : hash_id(key));
   sos_Int ht_pos = org_hash_value MOD ht_entries;
   sos_Object result;

   ht_entry_t ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
   page_t page;
   sos_Int first_link = FIRST_LINK(ht_pos, ht_entry.local_depth);
   ht_pos = first_link;
   sos_Offset page_offset = ht_entry.page_list_offset;

   page_header_t page_header = read_page_header (ct, page_offset);
   sos_Int pages = page_header.pages;
   sos_Int entries_on_last_page = page_header.entries_on_last_page;
   sos_Int entries_on_page = max_page_entries_without_list;
   result = my_no_object;
   sos_Int pos = -1; // entspricht "nicht gefunden"
   for (sos_Int page_no = 1;
        (page_no<=pages) AND (pos == -1);
        page_no++)
   {  if (page_no == pages)
     entries_on_page = entries_on_last_page;

      read_page(FALSE, ct, page_offset, entries_on_page, page);
      pos = search_page_for_key ( key_based_on_equal, page, entries_on_page,
                                  org_hash_value, key );
      if (pos == -1)
      {  page_offset = page.page_header.next_page;
         result = make_Object(page.entry[entries_on_page-1].key);
      }
      else
      {     // Findet sich der Vorgaenger auf derselben Seite ?
         if (pos > 0)
            result = make_Object(page.entry[pos-1].key);
         else
         {     // Falls eine vorherige Seite in der seitenliste
               // existiert, so wurde ihr letzter Eintrag in
               // result bereits gesetzt. Ist es jedoch die erste Seite
               // muss auf eine vorherige Seitenliste gegangen werden
            if (page_no == 1)
            {  sos_Bool found = FALSE;
               do
               {  ht_pos--;
                  do
                  {  if (ht_pos >= 0)
                     {     // suche den naechsten ersten verweis ab ht_pos;
                        ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
                        first_link = FIRST_LINK(ht_pos, ht_entry.local_depth);

                        if (first_link != ht_pos)
                           ht_pos--;
                      }
                  } while ((first_link != ht_pos) AND (ht_pos >= 0));

                  if (ht_pos >= 0)
                  {  page_header =
                       read_page_header(ct,ht_entry.page_list_offset);

                        // Falls auf dieser Seitenliste ein
                        // Eintrag ist, lese ihn, sonst bleibt found == FALSE
                     if ((page_header.pages > 1) OR
                         (page_header.entries_on_last_page > 0))
                     {  found = TRUE;
                           // lese letzte Seite
                        sos_Int i = read_page(FALSE, ct,page_header, ht_entry,
                                          page_header.pages, page);
                        result = make_Object(page.entry[i-1].key);
                     }
                  }
               } while ((NOT found) AND (ht_pos >= 0));
            }
         }
      }
   }

   return result;
} // ** get_pred **

// **************************************************************************
sos_Object get_succ ( sos_Container  ct,
                      sos_Bool       key_based_on_equal,
                      sos_Object     my_no_object,
                      sos_Int        ht_entries,
                      sos_Offset     ht_offset,
                      sos_Object     key)
// **************************************************************************
{  sos_Int org_hash_value = absolute((key_based_on_equal)?
                                     key.hash_value() : hash_id(key));
   sos_Int ht_pos = org_hash_value MOD ht_entries;
   sos_Object result;

   ht_entry_t ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
   page_t page;
   sos_Int first_link = FIRST_LINK(ht_pos,ht_entry.local_depth);
   ht_pos = first_link;
   sos_Offset page_offset = ht_entry.page_list_offset;

   page_header_t page_header = read_page_header (ct, page_offset);
   sos_Int pages = page_header.pages;
   sos_Int entries_on_last_page = page_header.entries_on_last_page;
   sos_Int entries_on_page = max_page_entries_without_list;
   result = my_no_object;
   sos_Int pos = -1; // entspricht "nicht gefunden"
   for (sos_Int page_no = 1; (page_no<=pages) AND (pos == -1); page_no++)
   {  if (page_no == pages)
     entries_on_page = entries_on_last_page;

      read_page(FALSE, ct, page_offset, entries_on_page, page);
      pos = search_page_for_key ( key_based_on_equal, page, entries_on_page,
                                  org_hash_value, key );
      if (pos == -1)
         page_offset = page.page_header.next_page;
      else
      {     // Findet sich der Nachfolger auf derselben Seite ?
         if (pos < entries_on_page-1)
            result = make_Object(page.entry[pos+1].key);
         else
         {  if (page_no < page_header.pages)
            {  read_page(FALSE, ct, page.page_header.next_page, 1, page);
               result = make_Object(page.entry[0].key);
            }
            else
            {     // Der Schluessel ist der letzte Eintrag auf der
                  // Seitenliste, der Nachfolger ist auf der
                  // naechsten Seitenliste
               sos_Bool found = FALSE;
               do
               {  ht_pos++;
                  do
                  {     // suche den naechsten ersten verweis ab ht_pos;
                        // read ht_entry
                     if (ht_pos < ht_entries)
                     {  ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
                        first_link = FIRST_LINK(ht_pos,ht_entry.local_depth);
                        if (first_link != ht_pos)
                           ht_pos++;
                     }
                   } while ((first_link != ht_pos) AND (ht_pos < ht_entries));

                   if (ht_pos < ht_entries)
                   {     // lese den Seitenkopf und das erste
                         // Objekt dieser Seite
                      read_page(FALSE,ct, ht_entry.page_list_offset, 1, page);
                      if ((page.page_header.pages > 1) OR
                          (page.page_header.entries_on_last_page > 0))
                      {  found = TRUE;
                         result = make_Object(page.entry[0].key);
                      }
                  }
               } while ((NOT found) AND (ht_pos < ht_entries));
            }
         }
      }
   }

   return result;
} // ** Mapping::get_succ **


// **************************************************************************
sos_Object sos_Object_sos_Object_Mapping::search_succ_pred
                                             (sos_Object key, sos_Int steps)
// **************************************************************************
{  T_PROC("Mapping::search_succ_pred");
   TT(agg_M, T_ENTER; TI (steps));

   sos_Container ct             = self.container();
   sos_Bool key_based_on_equal  = self.get_key_based_on_equal();
   sos_Bool list_cursor         = self.get_list_cursor();
   sos_Object my_no_object      = self;
   sos_Int ht_entries           = self.get_ht_entries();
   sos_Offset ht_offset         = self.get_ht_offset();
   sos_Object dummy_info;  // wird in get_entry nicht angefasst

   for (;steps != 0;)
   {  sos_Object pred,succ;
      if (list_cursor)
      {  get_entry(ct, list_cursor, key_based_on_equal,
                   ht_entries,ht_offset,
                   key, FALSE, dummy_info, pred,succ);
         if (steps > 0)
         {  if (succ == my_no_object)
        {  TT(agg_M, T_LEAVE);
               return my_no_object;
            }
            key = succ;
            steps--;
         }
         else
         {  if (pred == my_no_object)
        {  TT(agg_M, T_LEAVE);
               return my_no_object;
            }
            key = pred;
            steps++;
         }
      }
      else
      {  if (steps > 0)
         {  succ = get_succ(ct,key_based_on_equal,my_no_object,
                            ht_entries,ht_offset,key);
            if (succ == my_no_object)
        {  TT(agg_M, T_LEAVE);
               return my_no_object;
            }
            key = succ;
            steps--;
         }
         else
         {  pred = get_pred(ct,key_based_on_equal,my_no_object,
                            ht_entries,ht_offset,key);
            if (pred == my_no_object)
            {  TT(agg_M, T_LEAVE);
           return my_no_object;
            }
            key = pred;
            steps++;
         }
      }
   }
   TT(agg_M,T_LEAVE);
   return key;
} // ** Mapping::search_succ_pred **


// **************************************************************************
sos_Object read_last_object(sos_Container ct,
                            sos_Offset    ht_offset,
                            sos_Int       length,
                            sos_Object    my_no_object,
                            sos_Int       ht_entries)
// **************************************************************************
{  sos_Int ht_pos = ht_entries-1;
   sos_Bool found = FALSE;
   if (length == 0)
       return my_no_object;
   sos_Object result;
   ht_entry_t ht_entry;
   page_t page;
   page_header_t page_header;
   sos_Int first_link;
   do
   {  do
      {     // suche den vorherigen ersten Verweis ab ht_pos rueckwaerts
         ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
         first_link = FIRST_LINK(ht_pos,ht_entry.local_depth);
         if (first_link != ht_pos)
             ht_pos--;
      } while (first_link != ht_pos);

         // lese den page_header um festzustellen, ob auf der
         // Seitenliste ein Objekt ist
      page_header = read_page_header(ct,ht_entry.page_list_offset);
      if ((page_header.pages > 1) OR
          (page_header.entries_on_last_page > 0))
      {  found = TRUE;
            // lese letzte Seite
         read_page(FALSE,ct ,page_header, ht_entry, page_header.pages, page);
         result=make_Object(page.entry[page_header.entries_on_last_page-1].key);
      }
      else
         ht_pos--;
   } while (NOT found);

   return result;
} // ** Mapping::read_last_object **

// **************************************************************************
sos_Object read_first_object(sos_Container ct,
                             sos_Offset    ht_offset,
                             sos_Int       length,
                             sos_Object    my_no_object)
// **************************************************************************
{   sos_Int ht_pos = 0;
    sos_Bool found = FALSE;
    if (length == 0)
       return my_no_object;
    sos_Object result;
    ht_entry_t ht_entry;
    page_t page;
    sos_Int first_link;

    do
    {  do
       {     // suche den naechsten ersten verweis ab ht_pos;
             // read ht_entry
          ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
          first_link = FIRST_LINK(ht_pos,ht_entry.local_depth);
          if (first_link != ht_pos)
             ht_pos++;
       }
       while (first_link != ht_pos);

       // lese die Seite und das erste Objekt von diesem Verweis
       read_page(FALSE, ct, ht_entry.page_list_offset, 1, page);
       if ((page.page_header.pages > 1) OR
           (page.page_header.entries_on_last_page > 0))
       {  found = TRUE;
          result = make_Object(page.entry[0].key);
       }
       else
          ht_pos++;
    } while (NOT found);
    return result;
} // ** Mapping::read_first_object **


// **************************************************************************
void destroy_ht (sos_Bool       list_cursor,
                 sos_Container  ct,
                 sos_Int        ht_entries,
                 sos_Int        global_depth,
                 sos_Offset     ht_offset)
// **************************************************************************
{  T_PROC("destroy_ht ");
   TT (agg_M, T_ENTER; TI(ht_entries); TI(global_depth));
      // loescht alle Eintrage und die Hashtabelle,

   ht_entry_t ht_entry;

   for (sos_Int ht_pos=0;ht_pos < ht_entries;ht_pos++)
   {  ht_entry = read_ht_entry(ct,ht_offset,ht_pos);
      sos_Int local_depth = ht_entry.local_depth;
         // Berechne denjenigen Teil des Hashwertes, der auf der
         // Seitenliste unterschieden wird, dies ist gleichzeitig
         // der erste Verweis auf die Seitenliste
      sos_Int hash_value_part = FIRST_LINK(ht_pos, local_depth);

         // Berechne den letzten Verweis auf diese Seiteliste
      sos_Int last_link = LSHIFT(LSHIFT(1,global_depth-local_depth)-1,
                             local_depth) BITAND hash_value_part;
         // es muss der letzte Verweis sein, andernfalls wuerde die Kiste
         // beim nachfolgenden Lesen der lokalen Tiefe abschmieren,
         // da die Seite schon deallokiert waere.

         // Falls der gefundendene Verweis der letzte auf diese Seitenliste
         // ist, so deallokiere diese
      if (last_link == ht_pos)
      {  page_header_t page_header =
             read_page_header(ct,ht_entry.page_list_offset);
         destroy_page_list(list_cursor, ct,
                           ht_entry.page_list_offset, page_header.pages);
      }
   }

   if (ht_entries>0)
      ct.deallocate(ht_offset,ht_entries*HT_ENTRY_SIZE);

   TT(agg_M,T_LEAVE);
} // ** Mapping::destroy_ht **

// **************************************************************************
void sos_Object_sos_Object_Mapping::init_table ()
// **************************************************************************
{  T_PROC("Mapping::init_table");
   TT(agg_H, T_ENTER);

      // create a hash-tab
      // Ein Eintrag besteht aus einem Offset
      // also einem Zeiger auf eine Seite
   self.set_ht_entries(1);
   sos_Container ct  = self.container();
   self.set_ht_offset(ct.allocate (self.get_ht_entries()*HT_ENTRY_SIZE));

      // no_of_pages[i] gibt an, wieviel Seiten mit der lokalen
      // Tiefe i existieren
   self.set_no_of_pages_offset(ct.allocate(NO_OF_PAGES_ARRAY_SIZE));
   sos_Char mem [NO_OF_PAGES_ARRAY_SIZE];
   for (sos_Int i = 0;i< NO_OF_PAGES_ARRAY_SIZE;i++) mem[i] = 0;
   ct.write(self.get_no_of_pages_offset(), NO_OF_PAGES_ARRAY_SIZE, &mem);

   ht_entry_t ht_entry;
   ht_entry.page_list_offset = ct.allocate(PAGE_SIZE(self.get_list_cursor()));
   ht_entry.local_depth = 0;
   write_ht_entry(ct, self.get_ht_offset(),0,ht_entry);

   page_header_t page_header;
   page_header.pages = 1;
   page_header.entries_on_last_page = 0;
   write_page_header(ct,ht_entry.page_list_offset,page_header);

   self.set_no_of_pages(1);
   self.set_no_of_page_lists(1);
   add_no_of_pages(ct,self.get_no_of_pages_offset(),0,1);

   TT(agg_H,T_LEAVE);
} // ** Mapping::init_table **

// **************************************************************************
void sos_Object_sos_Object_Mapping::local_initialize
                                       (sos_Object_sos_Object_Mapping map)
// **************************************************************************
{  T_PROC("Mapping::local_initialize");
   TT(agg_H, T_ENTER);

   sos_Object my_no_object = map;

   map.set_cardinality (0);
   map.set_first_object(my_no_object);
   map.set_last_object(my_no_object);
   map.set_ht_entries(0);
   map.set_global_depth(0);
   map.set_no_of_pages_offset(NIL);
   map.set_no_of_pages(0);
   map.set_ht_offset(NIL);

   TT(agg_H,T_LEAVE);
}; // ** Mapping::local_initialize **

// **************************************************************************
void sos_Object_sos_Object_Mapping::local_finalize
                                       (sos_Object_sos_Object_Mapping map)
// **************************************************************************
{  T_PROC("Mapping::local_finalize");
   TT (agg_H, T_ENTER);

   destroy_ht(map.get_list_cursor(), map.container(), map.get_ht_entries(),
              map.get_global_depth(), map.get_ht_offset());

   TT (agg_H, T_LEAVE);
} // ** Mapping::local_finalize **

// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::is_key (sos_Object key)
// **************************************************************************
{  T_PROC("Mapping::is_key");
   TT(agg_H, T_ENTER);
   sos_Object dummy_pred,dummy_succ,dummy_info;
   sos_Bool result = FALSE;
   sos_Object my_no_object = self;
   result = get_entry(self.container(), self.get_list_cursor(),
                      self.get_key_based_on_equal(),
                      self.get_ht_entries(), self.get_ht_offset(),
                      key, FALSE, dummy_info, dummy_pred,dummy_succ);
   TT(agg_H, T_LEAVE);
   return result;
} // ** Mapping::is_key **


// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::is_info (sos_Object info)
// **************************************************************************
// TRUE, falls info mit insert(*,info) in die Struktur
// aufgenommen wurde.
// Vorsicht !! nicht aufrufen !!
// Die Funktion hat einen Aufwand von o(Anzahl der Eintraege) !!
{  T_PROC("Mapping::is_info");
   TT(agg_H,T_ENTER);

   sos_Container  ct = self.container();
   sos_Bool       list_cursor = self.get_list_cursor();
   sos_Bool       info_based_on_equal = self.get_info_based_on_equal();
   ht_entry_t  ht_entry;
   page_t      page;
   sos_Object  key;

      // Durchlaufe die gesamte Hashtabelle
      // benutze jeden Verweis um die Seite zu durchsuchen,
      // verwende bei mehrfachen Verweisen nur den ersten
   sos_Int ht_entries = self.get_ht_entries();
   sos_Offset ht_offset = self.get_ht_offset();
   for (sos_Int ht_pos=0;
        ht_pos < ht_entries; // positiver Abbruch nur in der Schleife
        ht_pos++)
   {  ht_entry = read_ht_entry(ct,ht_offset,ht_pos);

         // Wie lautet der dieser Seite zugeordnete Hash-Wert ?
      sos_Int hash_value_part = (LSHIFT(1,ht_entry.local_depth)-1)
                                BITAND ht_pos;

         // Ist dieser Verweis der erste auf diese Seite ?
      if (hash_value_part == ht_pos)
      {     // Ja,
         sos_Offset page_offset = ht_entry.page_list_offset;
         page_header_t page_header = read_page_header(ct, page_offset);

         sos_Bool found = FALSE;
         sos_Int pages = page_header.pages;
     sos_Int entries_on_last_page = page_header.entries_on_last_page;
     sos_Int entries_on_page = MAX_PAGE_ENTRIES(list_cursor);
         for (sos_Int page_no = 1;
              (page_no<=pages) AND (NOT found);
              page_no++)
         {  if (page_no == pages)
           entries_on_page = entries_on_last_page;

            if (entries_on_page > 0)
               read_page(list_cursor, ct,page_offset,
                         entries_on_page, page);

               // Durchsuche die Seite nach dem Objekt
            for (sos_Int k=0;
                 (NOT found) AND (k<entries_on_page);
                 k++)
            {  key = make_Object(page.entry[k].info);
               found = agg_same_entity (key,info,info_based_on_equal,EQ_STRONG);
        }

            if (found)
            {  TT(agg_H,T_LEAVE);
               return TRUE;
            }

            page_offset = page.page_header.next_page;
         }
      }
   }

   TT(agg_H,T_LEAVE);
   return FALSE; // Pech ...
} // ** Mapping::is_info **

// **************************************************************************
void sos_Object_sos_Object_Mapping::insert(sos_Object Key, sos_Object Entity)
// **************************************************************************
{  T_PROC("Mapping::insert");
   TT(agg_H, T_ENTER);

   sos_Object my_no_object = self;
      // Das Mappingobjekt selbst wird als Methodenausgabe fuer ein ungueltiges
      // Objekt benutzt. Drum kann man NO_OBJECT, aber nicht das
      // Mappingobjekt einfuegen. Soll es auch auch eingefuegt werden koennen,
      // benoetigt man ein eigenes MAPPING_NO_OBJECT.
   if (Key == self)
      err_raise(err_USE,"Mapping itself cannot inserted","Mapping::insert");

      // fuege das Element in der Listen-Version hinten an die Liste
      // in der non-Listen Version haben die beiden letzten Parameter
      // pred und succ keine Wirkung
   self.insert_in_list(Key, Entity, self.get_last_object(), my_no_object);

   TT(agg_H,T_LEAVE);
} // ** Mapping::insert **

// **************************************************************************
void sos_Object_sos_Object_Mapping::remove (sos_Object key)
// **************************************************************************
{  T_PROC("Mapping::remove");

   sos_Bool found=FALSE;

   if (self.get_ht_entries() >0)
   {  sos_Container ct = self.container();
      sos_Int org_hash_value = absolute((self.get_key_based_on_equal())?
                                        key.hash_value():hash_id(key));
      sos_Int ht_pos         = org_hash_value MOD self.get_ht_entries();
      ht_entry_t ht_entry = read_ht_entry(ct,self.get_ht_offset(),ht_pos);
      found = make_sos_Bool(
      self.remove_from_page_list (ct, self.get_list_cursor(),
                              self.get_key_based_on_equal(),
                              ht_entry.page_list_offset,
                                  org_hash_value,key));
      sos_Object my_no_object = self;
      if (found)
      {     // Versuche, die Seitenliste zu verschmelzen
         if (self.assemble_page(ht_entry.page_list_offset,
                                ht_entry.local_depth,
                                org_hash_value))
               // versuche, die Hash-Tabelle zu verkleinern
            self.decrease_hash_table();
      }
   }
   TT(agg_H,T_LEAVE; TB(found));
}// ** Mapping::remove **

// **************************************************************************
sos_Object sos_Object_sos_Object_Mapping::operator[] (sos_Object key)
// **************************************************************************
{  T_PROC("Mapping::operator[]");
   TT(agg_H,T_ENTER);

   sos_Object dummy_pred,dummy_succ,info;
   sos_Container  ct = self.container();
   sos_Bool       key_based_on_equal = self.get_key_based_on_equal();
   sos_Bool       list_cursor = self.get_list_cursor();
   sos_Object     my_no_object = self;
   sos_Int        ht_entries = self.get_ht_entries();
   sos_Offset     ht_offset = self.get_ht_offset();

   if (NOT get_entry(ct, list_cursor,key_based_on_equal,ht_entries,
             ht_offset,key,TRUE, info, dummy_pred,dummy_succ))
      info = NO_OBJECT;

   TT(agg_H,T_LEAVE);
   return info;
} // ** Mapping::operator[] **

// **************************************************************************
sos_Object sos_Object_sos_Object_Mapping::get_key(sos_Cursor c)
// **************************************************************************
{  T_PROC("Mapping::get_key(sos_Cursor)");
   TT(agg_H, T_ENTER);

   err_assert (c.defined_for (self), "Mapping:get_key");
   err_assert (self.is_valid(c), "Mapping:get_key");

   sos_Map_node mn = sos_Map_node::make (c.get_current());
   sos_Object   o  = mn.get_key_val();

   TT(agg_H,T_LEAVE);
   return o;
} // ** Mapping::get_key **

// **************************************************************************
sos_Object sos_Object_sos_Object_Mapping::get_info(sos_Cursor c)
// **************************************************************************
{  T_PROC("Mapping::get_info(sos_Cursor)");
   TT(agg_H, T_ENTER);

   err_assert (c.defined_for (self), "Mapping:get_info");
   err_assert(self.is_valid(c),"Mapping:get_info");

   sos_Object my_no_object = self;
   sos_Object dummy_pred,
          dummy_succ;

   sos_Object key = sos_Map_node::make (c.get_current()).get_key_val();
   sos_Object info;
   sos_Bool found = get_entry(self.container(), self.get_list_cursor(),
                              self.get_key_based_on_equal(),
                              self.get_ht_entries(), self.get_ht_offset(),
                              key,TRUE, info,dummy_pred,dummy_succ);
      // Beliebter Benutzerfehler: Ein Prozess erzeugt
      // einen Eintrag mit einem Key im TEMP_CONTAINER, das
      // Programm beendet, ein anderer Prozess versucht darueber
      // zu itterieren. Trotz das im Key Bockmist steht, kann er
      // noch mit get_key geliefert werden. Wenn jedoch der passende Eintrag
      // dazu gesucht wird, wird der Hashwert vom Key gebraucht. In diesem
      // stehen wilde Sachen, der Eintrag wird (vermutlich) nicht gefunden.
   if (NOT found)
      err_raise(err_USE,"Entry didn't exists anymore","Mapping::get_info");

   TT(agg_H, T_LEAVE);
   return info;
} // ** Mapping::get_info **

// **************************************************************************
void sos_Object_sos_Object_Mapping::set_info(sos_Cursor c, sos_Object o)
// **************************************************************************
{  T_PROC ("Mapping::set_info");
   TT (agg_H, T_ENTER);

   err_assert ((c.defined_for (self)), "Mapping:set_info");
   self.insert (sos_Map_node::make (c.get_current()).get_key_val(), o);

   TT (agg_H, T_LEAVE);
} // ** Mapping::set_info **

// **************************************************************************
void sos_Object_sos_Object_Mapping::move_cursor(sos_Cursor c, sos_Object key)
// **************************************************************************
// sets the cursor c to the key object in the mapping that corresponds
// to the given key
{  T_PROC ("Mapping::move_cursor");
   TT( agg_H, T_ENTER);

   err_assert (c.defined_for (self), "Mapping:move_cursor");
   err_assert (self.is_key(key), "Mapping:move_cursor");

   sos_Object dummy_pred, dummy_succ, dummy_info;
   sos_Bool found = get_entry(self.container(), self.get_list_cursor(),
                              self.get_key_based_on_equal(),
                              self.get_ht_entries(),self.get_ht_offset(),
                              key,FALSE, dummy_info, dummy_pred,dummy_succ);
   err_assert (found, "Mapping:move_cursor");
   sos_Map_node::make (c.get_current()).set_key_val(key);

   TT(agg_H, T_LEAVE);
} // ** Mapping::move_cursor **

// **************************************************************************
void sos_Object_sos_Object_Mapping::insert_before (sos_Cursor c,
                                                   sos_Object Key,
                                                   sos_Object Entity)
// **************************************************************************
{  T_PROC("Mapping::insert_before");
   TT(agg_H, T_ENTER);

   err_assert (self.get_list_cursor(), "Mapping:insert_before");
   err_assert (c.defined_for (self), "Mapping:insert_before");
   err_assert (self.is_valid(c), "Mapping:insert_before");

   if (Key == self)
      err_raise(err_USE,"Mapping itself cannot inserted","Mapping::insert");
   sos_Map_node mn = sos_Map_node::make (c.get_current());

   sos_Object dummy_info,pred,dummy_succ;
   sos_Object key = mn.get_key_val();
   get_entry(self.container(), self.get_list_cursor(),
             self.get_key_based_on_equal(),
             self.get_ht_entries(),self.get_ht_offset(),
             key,FALSE, dummy_info, pred,dummy_succ);
   self.insert_in_list(Key, Entity, pred, mn.get_key_val());

   TT(agg_H, T_LEAVE);
} // ** Mapping::insert_before **

// **************************************************************************
void sos_Object_sos_Object_Mapping::insert_after (sos_Cursor c,
                                                  sos_Object Key,
                                                  sos_Object Entity)
// **************************************************************************
{  T_PROC("Mapping::insert_after");
   TT(agg_H, T_ENTER);

   err_assert (self.get_list_cursor(), "Mapping:insert_after");
   err_assert (c.defined_for (self), "Mapping:insert_after");
   err_assert (self.is_valid(c), "Mapping:insert_after");

   if (Key == self)
      err_raise(err_USE,"Mapping itself cannot inserted","Mapping::insert");

   sos_Map_node mn = sos_Map_node::make (c.get_current());

   sos_Object dummy_info,dummy_pred,succ;
   sos_Object key = mn.get_key_val();
   get_entry(self.container(), self.get_list_cursor(),
             self.get_key_based_on_equal(),
             self.get_ht_entries(),self.get_ht_offset(),
             key,FALSE,dummy_info,dummy_pred,succ);
   self.insert_in_list(Key, Entity, mn.get_key_val(), succ);

   TT(agg_H, T_LEAVE);
} // ** Mapping::insert_after **

// **************************************************************************
void sos_Object_sos_Object_Mapping::local_assign
                                       (sos_Object_sos_Object_Mapping x,
                                        sos_Object                    o)
// **************************************************************************
{  T_PROC("Mapping::local_assign");

   sos_Object_sos_Object_Mapping y = sos_Object_sos_Object_Mapping::make (o);
   sos_Container y_ct = y.container();
   sos_Container x_ct = x.container();
   sos_Bool x_list_cursor = x.get_list_cursor();

   err_assert ((y.get_list_cursor() == x_list_cursor),
               "Mapping::local_assign");

   destroy_ht(x_list_cursor, x_ct, x.get_ht_entries(),
              x.get_global_depth(), x.get_ht_offset());

   sos_Bool key_based_on_equal = y.get_key_based_on_equal();
   sos_Bool info_based_on_equal= y.get_info_based_on_equal();
   sos_Int cardinality         = y.get_cardinality();
   sos_Int no_of_pages         = y.get_no_of_pages();
   sos_Int no_of_page_lists    = y.get_no_of_page_lists();
   sos_Int global_depth        = y.get_global_depth();
   sos_Int ht_entries          = y.get_ht_entries();
   sos_Int no_of_pages_offset  = y.get_no_of_pages_offset();

   x.set_key_based_on_equal(key_based_on_equal);
   x.set_info_based_on_equal(info_based_on_equal);
   x.set_cardinality(cardinality);
   x.set_no_of_pages(no_of_pages);
   x.set_no_of_page_lists(no_of_page_lists);
   x.set_global_depth(global_depth);
   x.set_ht_entries(ht_entries);
   x.set_first_object(y.get_first_object());
   x.set_last_object(y.get_last_object());


   if (cardinality != 0)
   {    // kopiere das Feld fuer no_of_pages rueber
      sos_Offset new_no_of_pages_offset = x_ct.allocate(NO_OF_PAGES_ARRAY_SIZE);
      x.set_no_of_pages_offset(new_no_of_pages_offset);
      sos_Char mem [NO_OF_PAGES_ARRAY_SIZE];
      y_ct.read(no_of_pages_offset, NO_OF_PAGES_ARRAY_SIZE, &mem);
      x_ct.write(new_no_of_pages_offset, NO_OF_PAGES_ARRAY_SIZE, &mem);

         // erzeuge die Hashtabelle
      x.set_ht_offset(x_ct.allocate(y.get_ht_entries() *HT_ENTRY_SIZE));
         // Laufe die erste HT durch und kopiere die Seiten
      sos_Offset old_ht_offset = y.get_ht_offset();
      sos_Offset new_ht_offset = x.get_ht_offset();
      for (sos_Int ht_pos = 0;ht_pos<y.get_ht_entries();ht_pos++)
      {  ht_entry_t ht_entry = read_ht_entry(y_ct,old_ht_offset,ht_pos);

            // Ist es der erste Zeiger auf die Seitenliste ?
         sos_Int local_depth = ht_entry.local_depth;
         sos_Int first_link = FIRST_LINK(ht_pos, local_depth);
         if (first_link == ht_pos)
         {     // erster Verweis, kopiere die Seitenliste
            sos_Offset old_page_offset = ht_entry.page_list_offset;
            page_header_t  old_first_page_header =
                read_page_header(y_ct, ht_entry.page_list_offset);

            sos_Offset pred_page_offset=0;

            for(sos_Int page_no=1;page_no<=old_first_page_header.pages;page_no++)
            {  sos_Offset new_page_offset =
          x_ct.allocate(PAGE_SIZE(x_list_cursor));
               if (page_no == 1)
                  ht_entry.page_list_offset = new_page_offset;
               else
               {  page_header_t tmp_page_header = old_first_page_header;
                  tmp_page_header.next_page = new_page_offset;
                  // schreibe den Seitenverweis in den Vorgaenger
                  write_page_header(x_ct,pred_page_offset, tmp_page_header);
               }

               page_t tmp_page;
               sos_Int entries = (page_no < old_first_page_header.pages)?
                                 MAX_PAGE_ENTRIES(x_list_cursor):
                                 old_first_page_header.entries_on_last_page;

                  // kopiere die Seite
               read_page(x_list_cursor,y_ct,old_page_offset,entries,tmp_page);
               write_page(x_list_cursor, x_ct,new_page_offset,
                          MAX_PAGE_ENTRIES(x_list_cursor), tmp_page);
               pred_page_offset = new_page_offset;

                  // lese den Seitenkopf der Seite, um
          // Nachfolgerseite rauszufinden
               page_header_t old_page_header =
                  read_page_header(y_ct,old_page_offset);

               old_page_offset = old_page_header.next_page;
            } // kopiere alle Seiten

               // schreibe den HT-Eintrag in alle Verweise der HT
            sos_Int no_of_links = LSHIFT(1,global_depth-local_depth);
            for (sos_Int k=0;k<no_of_links;k++)
            {  sos_Int x = LSHIFT(k,local_depth);
               sos_Int other_link = x BITOR ht_pos;
               write_ht_entry(x_ct,new_ht_offset,other_link,ht_entry);
            } // schreibe alle HT-Eintraege pro Seite
         }
      }
      if (x_list_cursor)
      {  sos_Object my_no_object = x;
         x.write_succ_pred
            (x_ct, key_based_on_equal, x_list_cursor,
             x.get_first_object(), FALSE, my_no_object);
         x.write_succ_pred
            (x_ct, key_based_on_equal, x_list_cursor,
             x.get_last_object(), TRUE, my_no_object);
      }
   }
   else
   {     // Kein Element drin, erzeuge nichts, initialisere wie in local_init
      sos_Object my_no_object = x;
      x.set_first_object(my_no_object);
      x.set_last_object(my_no_object);
      x.set_ht_offset(NIL);
      x.set_ht_entries(0);
      x.set_no_of_pages_offset(NIL);
   }

   TT(agg_H,T_LEAVE);
} // ** Mapping::local_assign **

// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::local_equal
                                       (sos_Object_sos_Object_Mapping x,
                                        sos_Object                    o,
                                        sos_Eq_kind                   eq_kind)
// **************************************************************************
{  sos_Bool result;

   if ((eq_kind EQ EQ_STRONG AND NOT o.has_type(x.type())) OR
       (eq_kind EQ EQ_WEAK   AND NOT o.isa     (x.type())))
      result = FALSE;
   else
   {  sos_Object_sos_Object_Mapping y =
         sos_Object_sos_Object_Mapping::make (o);
      if (y.get_cardinality() != x.get_cardinality())
         result = FALSE;
      else
      {  sos_Bool info_based_on_equal = x.get_info_based_on_equal();
         agg_iterate_association (x, sos_Object key, sos_Object info)
         {  if (NOT agg_same_entity (y[key],info,info_based_on_equal,eq_kind))
            {  result = FALSE;
               break;
            }
         }
         agg_iterate_association_end (x, key, info);
      }
   }

   return result;
} // ** Mapping::local_equal **

// **************************************************************************
sos_Int sos_Object_sos_Object_Mapping::local_hash_value
                                       (sos_Object_sos_Object_Mapping m)
// **************************************************************************
// Ansich muesste der augenblickliche Hashwert gespeichert werden, und bei
// jedem eingefuegten Element mit einer reversiblen Operation verknuepft
// werden. Bei jedem remove, muss diese reversible Operation aufgerufen
// werden. Zu viel Aufwand, drum bisher noch nicht implementiert.
{  return m.card();
} // ** Mapping::local_hash_value **

// **************************************************************************
sos_Int sos_Object_sos_Object_Mapping::size()
// **************************************************************************
{  sos_Int o_size = sos_Object::size();
   sos_Int ht_size = self.get_ht_entries() * HT_ENTRY_SIZE;
   sos_Int nop_size = (ht_size>0)?NO_OF_PAGES_ARRAY_SIZE:0;
   sos_Int pg_size = self.get_no_of_pages()*PAGE_SIZE(self.get_list_cursor());
   return o_size +
          self.container().rounded (ht_size) +
          self.container().rounded (pg_size) +
          self.container().rounded (nop_size);
} // ** Mapping::size **

// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::is_role1 (sos_Object key)
// **************************************************************************
{  return self.is_key (key);
} // ** Mapping::is_role1 **

// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::is_role2 (sos_Object info)
// **************************************************************************
{  return self.is_info (info);
} // ** Mapping::is_role2 **

// **************************************************************************
sos_Object sos_Object_sos_Object_Mapping::get_role1 (sos_Cursor c)
// **************************************************************************
{  return self.get_key (c);
} // ** Mapping::get_role1 **

// **************************************************************************
sos_Object sos_Object_sos_Object_Mapping::get_role2 (sos_Cursor c)
// **************************************************************************
{  return self.get_info (c);
} // ** Mapping::get_role2 **

// **************************************************************************
void sos_Object_sos_Object_Mapping::remove_at(sos_Cursor c)
// **************************************************************************
{  T_PROC("Mapping::remove_at");
   TT(agg_H, T_ENTER);

   err_assert (c.defined_for (self), "Mapping:remove_at");
   err_assert (self.is_valid(c), "Mapping:remove_at");

   sos_Object key = self.get_key(c);

   if (self.get_list_cursor())
      self.to_succ(c);
   else
   {     // Setze Cursor auf my_no_object => is_valid == FALSE
      sos_Object my_no_object = self;
      sos_Map_node mn = sos_Map_node::make (c.get_current());
      mn.set_key_val(my_no_object);
   }

   self.remove(key);

   TT(agg_H, T_LEAVE);
} // ** Mapping::remove_at **

// **************************************************************************
void sos_Object_sos_Object_Mapping::clear()
// **************************************************************************
{  T_PROC("Mapping::clear");
   TT(agg_H, T_ENTER);

   sos_Container ct = self.container();
   sos_Int ht_entries = self.get_ht_entries();
   if (ht_entries >0)
      destroy_ht(self.get_list_cursor(), ct, ht_entries,
                 self.get_global_depth(), self.get_ht_offset());

   sos_Object my_no_object = self;
   self.set_first_object(my_no_object);
   self.set_last_object(my_no_object);
   self.set_cardinality (0);
   self.set_ht_entries(0);
   self.set_global_depth(0);
   self.set_no_of_pages_offset(NIL);
   self.set_no_of_pages(0);
   self.set_ht_offset(NIL);

   TT(agg_H, T_LEAVE);
} // ** Mapping::clear **

// **************************************************************************
sos_Int sos_Object_sos_Object_Mapping::card ()
// **************************************************************************
{  T_PROC ("Mapping::card");
   TT (agg_H, T_ENTER);

   sos_Int crd = self.get_cardinality();

   TT (agg_H, T_LEAVE);
   return crd;
} // ** Mapping::card **

// **************************************************************************
sos_Cursor sos_Object_sos_Object_Mapping::open_cursor(sos_Container Cursor_ct)
// **************************************************************************
{  T_PROC ("Mapping::open_cursor");
   TT( agg_H, T_ENTER);

   sos_Cursor c = sos_Cursor::create(Cursor_ct, self);
   sos_Map_node mn = sos_Map_node::create(Cursor_ct);
   c.set_current(mn);

   self.to_first(c);

   TT(agg_H, T_LEAVE);
   return c;
} // ** Mapping::open_cursor **

// **************************************************************************
void sos_Object_sos_Object_Mapping::close_cursor(sos_Cursor c)
// **************************************************************************
{  err_assert ((c.defined_for (self)), "Mapping:close_cursor");
   c.get_current().destroy();
   c.destroy();
} // ** Mapping::close_cursor **

// **************************************************************************
sos_Cursor sos_Object_sos_Object_Mapping::duplicate(sos_Cursor c)
// **************************************************************************
{  err_assert ((c.defined_for (self)), "Mapping:duplicate");
   sos_Container Cursor_ct = c.container();

   sos_Cursor dup_c = sos_Cursor::create(Cursor_ct, self);
   sos_Map_node dup_mn = sos_Map_node::create(Cursor_ct);

   dup_c.set_current (dup_mn);
   dup_mn.set_key_val (sos_Map_node::make (c.get_current()).get_key_val());

   return dup_c;
} // ** Mapping::duplicate **

// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::is_valid (sos_Cursor c)
// **************************************************************************
{  sos_Map_node mn           = sos_Map_node::make (c.get_current());
   sos_Object   my_no_object = self;
   sos_Bool     valid        = (mn.get_key_val() != my_no_object);

   return valid;
} // ** is_valid **

// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::to_first(sos_Cursor c)
// **************************************************************************
{  err_assert ((c.defined_for (self)), "Mapping:to_first");
   sos_Container Cursor_ct = c.container();
   sos_Map_node  current = sos_Map_node::make (c.get_current());
   sos_Object    my_no_object = self;
   sos_Object    first;

   if (self.get_cardinality() > 0)
   {  if (NOT (self.get_list_cursor()))
         first = read_first_object(self.container(),self.get_ht_offset(),
                                   self.get_cardinality(),my_no_object);
      else
         first = self.get_first_object();
   }
   else
      first = my_no_object;

   current.set_key_val(first);

   return self.is_valid(c);
} // ** Mapping::to_first **

// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::to_last(sos_Cursor c)
// **************************************************************************
{  err_assert ((c.defined_for (self)), "Mapping:to_last");
   sos_Map_node  current      = sos_Map_node::make (c.get_current());
   sos_Container Cursor_ct    = c.container();
   sos_Object    my_no_object = self;
   sos_Object    last;

   if (self.get_cardinality() > 0)
   {  if (NOT (self.get_list_cursor()))
         last = read_last_object
                   (self.container(),
                    self.get_ht_offset(),self.get_cardinality(),
                    my_no_object,self.get_ht_entries());
      else
         last = self.get_last_object();
   }
   else
      last = my_no_object;

   current.set_key_val(last);

   return self.is_valid(c);
} // ** Mapping::to_last **

// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::to_succ(sos_Cursor c, Index i)
// **************************************************************************
{  err_assert (c.defined_for (self), "Mapping:to_succ");
   err_assert (self.is_valid(c), "Mapping:to_succ");

   sos_Map_node mn = sos_Map_node::make (c.get_current());
   sos_Object   o  = self.search_succ_pred (mn.get_key_val(),i);

   mn.set_key_val (o);

   return self.is_valid (c);
} // ** Mapping::to_succ **

// **************************************************************************
sos_Bool sos_Object_sos_Object_Mapping::to_pred(sos_Cursor c, Index i)
// **************************************************************************
{  return self.to_succ(c,-i);
} // ** Mapping::to_pred **